Hi Alex,
There is good diving in that area, although my only land-based has been from Recife, a bit to the south of Natal.
For my money, Fernando de Noronha is the hot venue up that way. Here is my last trip report:
"Brazil is bigger than the continental US, with 4,600 miles of coastline -- it would be a little surprising if there wasn't some good diving. You'll need to fly north of Rio some, around Recife (Expedicao Atlantico; 011-5581-227-0458) & Angra dos Reis (Aquamaster Dive Center; 011-5524-365-2416) where there are some nice reefs. Recife has over a dozen wrecks, and dive conditions do not change appreciably from season to season.
The real action is an hour flight from Recife, at Fernando de Noronha, which you must book far in advance (like now) as it is in a marine park with limited attendance (Atlantis Divers; phone/fax; 011-5581-619-1371; divers@elogica.com.br). Can also try DUET Travel at 800-990-3839. Is a breeding area for spinner dolphin, & both green & hawksbill turtles. Fourteen species of shark are around, especially grays. I saw a jewfish as big as a VW (well, almost) when I was there. Large variety of tropicals in large schools. Look for viz of 60-100' & water temps in low 80s. Can be strong currents. Problem with Noronha is many of the best dives are at or below recreational limits -- like some of the pinnacles & the wreck of the Ipiranga. Best to be prepared for some deco dives, although most dives are within recreational & NDL. Accommodations are almost entirely B&Bs and posadas -- nothing luxurious there. Stayed at Pousada de Ze Maria which is cool, done in beautiful woods, & has both mountain & water views.
If you're thinking of carnival, have done it & it is some very nasty partying. The national sugar cane liquor is quite potent, not to mention the dental floss bikinis. Rio is like fitness insane, with aerobics classes on the beach starting at 5:00AM & fitness clubs or dance studios in every other store front. Best do the diving first."
Hope this was at least somewhat helpful.
DocVikingo