So here is an interesting addition to my problem.
At a LAN party at my friends house at the moment (Comcast provider) and we are all logged in.
All ports open, router and modem are working fine, and have been forever. I go to leave my mog house, exiting to Port Jeuno, and get stuck at the same downloading data screen.

Here's the retarded part - my friend leaves his mog house to port jeuno and can get in fine without any problems.
So I go to log in my character on his laptop to move mine out of Jeuno just to get me unstuck...still sat at the downloading data screen which resulted in the same FFXI-3001 error.
So even on a different computer, I can't login to move my character out of jeuno. Instead, I had to ask my friend in GEORGIA to log me in and move me. End result = it worked.

This thread has grown to 7 pages of people all complaining about similar issues. Something is clearly wrong, SE.
I believe its time for some answers.