Port forwarding settings of your router may be the answer –it was for me.
The following info is from Playonline's
Knowledge Base ()
PlayOnline(including all related software such as FINAL FANTASY XI) may use any of the following ports. If you are using a router, please configure it to allow packets to pass through these ports.Port numbers that may be used by the PlayOnline server group.TCP 25, 80, 110, 443 or 50000 - 65535UDP 50000 - 65535Port numbers that may be used by terminals such as the PlayStation 2.TCP 1024 - 65535UDP 50000 - 65535*Your router may require that you use a PC to configure your network settings. For more information about how to configure your network settings, please refer to the instruction manual that came with your router or contact the manufacturer directly.*If your Internet service provider (ISP) specifies a DNS server, you may need to configure your settings to allow packets to pass through UDP Port 53 as well. For more information, please refer to the instruction manual for your router or the information provided by your ISP.
I had issues with the suggested FFXI PC settings but when adding the ports 1024-65535 (for PS2 configurations) it worked.