Skype and Firewall Problem

I run Skype on my work laptop. We use the Zone Labs Integrity Agent Client Firewall and I cannot view or change the settings. I was running Skype version 2 OK until I upgraded it yesterday to the latest release. Now it will not connect. I was reading that Skype randomly changes the port on each installation to prevent NAT congestion if there are multiple users behind a router. Skype is now trying to use port 29561 for incoming traffic. I have no idea what port it was using when it was working before the upgrade. Is there any range port that would be more likely to work through a firewall? I know it is not my router because I configured my IP address to be outside the router firewall and it still cannot connect. Skype works on my other laptop through the same router. I am 99% sure it is the company firewall software that is blocking me.

I tried completely removing and re-installing a clean install of Skype with no success.