Well windows ME does not have a build in firewall. Some DSL modems do however, perhaps you are connected through cable or DSL?
Was it just noton anti-virus or norton internet security? Norton internet security comes with it's own firewall.
The other question is: are you sure you tried a working Palace?
palace://practice.thepalace.com
That definately works and you can try the instant Palace and the client on that one here:
http://practice.chatserve.com/ip.html