The biggest problem with going to Brazil is that they require a visa. That's always a big negative. Have a look at the embassy web site for details. I used Zierer, a visa service that costs more money than just sending your passport to the consulate, but minimizes the chance of a lost passport.
There are very few flights to Fernando de Noronha. I think only two airlines, Varig and Trip, fly there. I flew over on Varig in a modern, well maintained jet. The flight back was on Trip, on an ATR turboprop. Those are nice planes, but this is the most poorly maintained I've ever seen. There was a lot of interior trim broken. Made me wonder about the engine and avionics maintenance.
There's a great web page at airwise.com that will list all flights between different locations. I wish I know of an equivalent that listed flights going in or out of an airport from anywhere. It would make the search for possible connections a lot easier.
The travel agency brazil.com had a lot of packages to different places. I tried them to Fernando de Noronha, but they weren't able to get flights. Maybe they only deal with Varig and not Trip. They did seem like very knowledgeable people.
I got my tour package from Paulo Cavalcante (paulinho@grandesviagens.com.br).
His telephone number is (+55) (85) 244 5859.
He speaks both English and Spanish. However, it may not work out to call
or email him because he didn't want to take a credit card. I guess working
with him is only an option if you're already in Brazil.
Links
http://www.geocities.com/TheTropics/4363/noronha/nogeo_e.htm
http://www.frommers.com/destinations/fernandodonoronha/
Up to Brazil page