I've explored the entire map. I've played an earth map, and circled the world in a sub. I've played a Pangaea and circled the globe by land. I can't think what else could be needed to accomplish this one.
The achievement is bugged. Look at this thread on GameFaqs to see the solution :)
Rather than having to go to another site for the solution, here it is.
To fix the Magellan achievement bug, navigate to your steamapps folder and drill down to:
Open GlobalDefines.xml in notepad
Change the 0 in the tags to 1.