Your best bet would be to disable the XP firewall and get a better firewall such as ZoneAlarm. I wasn't aware that there was any problem using any of the IM programs to chat with the XP firewall though, the unable to establish a connection problem may not be related to the XP firewall.
Firewalls often interfere with chat programs like that, usually when trying to directly connect to chat, IM, transfer files, etc. If only one end is behind a firewall, usually that person can initiate a transfer, but not always...tends to be buggy, depending on the firewall. As you mentioned, using ZA is the best bet, as it does permissions based on the application.