Have you opened the ports in your router/modems firewall?

1 - Find out the brand and model of your router
2 - Find your router on the list on www.portforward.com
3 - Scroll down and select FINAL FANTASY XI PC
4 - Follow the instructions, but instead of whatever ports it tells you, use the ones listed below.

This site will give you the information you need to figure out how to forward ports on your particular router.

The ports you need to open are 54992-55551 TCP/UDP and port 443 UDP open.