How Can i use Skype Behind Firewall

Hi All,
Hey I have Wathguard X700 Firewall and 60 PC’s behind that.Now i need to use skype.I know that skype use TCP and UDP port,So i have already Allowing ALL TCP and UDP outgoing as well HTTP and HTTPS.I am able to use yahoo messenger without any problem.In the Log file I could not see any blocking entry.Out side the office there is no problem with skype.from office i cannot login to skype.It’s keep on trying and show message thet you ‘may be behind firewall’.
If anybody used skype behibd firewall please help me.. :((:((

Thanks,
Kiran Konsaai.