To get to the starter nations in the past, you need to take alternate routes.
To get to Sandoria: Take the V. Inlet from L-6 in Jugner and follow that all the way south to the D-11 zone, zoning back into southern Jugner. From there, work your way north, toward the lake. Once at the lake, head westward toward the King Arthro spawn (the rocks are not there in the past that would block getting to that area). Follow that into a zone that will take you to E.ron (KRT in the present), and follow that to sandy.
To get to Windy: Head to D-8 in Meriphataud to zone into Fort Karugo Narugo. Once in there, follow that all the way south to the zone at E-13, and you'll zone into W.Sarta. Follow to windurst. (I did not attempt to travel to Windy yet)
To get to Bastok: Head to I-11 in Pashhow to arrive at Grauberg. Head SW towards the zoneline C-14 to zone into N.Gustaberg. Follow to bastok. (Didnt attempt this route yet either)
New maps are available on ffxi-atlas as well to help out.