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:
steamapps\common\sid meier's civilization v\Assets\Gameplay\XML
Open GlobalDefines.xml in notepad
<Row Name="CIRCUMNAVIGATE_FREE_MOVES"> <Value>0</Value> </Row>
Change the 0 in the tags to 1.