Sorry to hear about problems with getting into Frost. - Don't know the deal - the only thing I can think of is trying to travel along the shorelines to get there. That's what I would try at least. There are points all along Frost coast that you can get ashore so that won't be an issue - not sure about fatigue though - but I bet there's somewhere you can do it from. I think I'd try going into Talador - head to (northern?) coast and try from there.
Hope you guys have better luck at it soon - remember to try to pick up flightpaths on the way
Also if you have the item from Cinderfall (timeless) - once you get the effigy part done - turn around from gara - point towards Spires and launch yourself to get easy access to void lantern guys area.
Also - travel on a Strider for water walking - or use your waterstrider for water walk - and always try to travel with pet out when mounted - for the times you get dismounted by a mob - pet will grab the agro and you can run off (short camo usage helps) and fd. Also if you need it - mount speed glyph can come in handy when traversing areas to get items (when lower level) if your not in a guild especially.
Remember to enjoy the experience - might be our only story driven tame we will get - and feel good that we got this level of love.