It really depends on your firewall. The behaviour you mention could also be caused by a proxy between you and the net. It\'s really difficult to say.
It sounds like you\'re using zonealarm, (just from the description of the popup and language used) Zonealarm should permit the thing to go through. If you\'re behind another firewall, router, or proxy, that might be the problem, or if you\'re on an internal (NAT) network using a proxy, as that can cause problems if things aren\'t routed correctly.
Assuming that none of these are the problem, and windows XP, you can actually have multiple firewalls configured, and any one of these can be the problem (and the internet connection firewall is almost worthless, in my humble opinion). You might try disabling this, and if you don\'t have PC-Cillin, zonealarm makes a fairly good windows firewall (if that\'s not actually what you\'re using).
http://www.zonelabs.com, in and outward bound protection, with program permissions.
(zonealarm and PC-cillin are incompatible, btw, for the largest part)
Probably the first thing to try is to check your IP address. If it starts with 192, or 169, then you\'re probably on a NAT address, on an internal network. (usually 192.168.0.x, or 169.128.0.x) It also depends on your netmask, really. Nat is a major problem because you don\'t actually route through the internet, you\'re redirected, and if the stream isn\'t redirected (planeshift as I understand using UDP, which doesn\'t verify reception, a good thing, again in my humble opinion, because TCP would reverify each packet, potentially doubling server load) then you\'d be unable to log in.
Hope this helps at least narrow the problem, even if it is obfuscated maunderings of a cheetah bard.