I do not know which ports are used by ICQ but there is a rather simple solution to that.
You can do it two ways: 1. Set up a Sox proxy and use it for ICQ (that would be the cleanest solution)
2. Start ICQ and look in the live log of your packet filter to see which ports are denied and thus you can define that service and allow it in the packet filter
quote: ICQ Messaging, must be able to communicate with the ICQ server. This was done via port TCP 5190 to login.icq.com (previously 4000 UDP icq.mirabilis.com) and needs a bidirectional connection on this port number. ICQ Client to client connection is done using the TCP protocol, using port range 1024 - 65535. This means that the client needs an open listening ports within the mentioned range - 1024 to 65535. Opening all these ports is obviously impractical. The ICQ client can be configured to work with a firewall or proxy server see www.icq.com, but generally results in reduced ICQ functionality. If your using IP masquerading i.e NAT as most firewalls will, you will need a SOCKS proxy server to implement ICQ connectivity for more than one internal user.
Also, be aware that if ICQ can't connect on 5190, it will start trying all sorts of ports like http and other more commonly open ports.
