That is very weird, some machines on my domain can't connect to Skype when Kaspersky is installed/active. And even if do a fresh install on the same machines Skype stops working at the exact time that I install Kaspersky Endpoint Security 184.108.40.2061 with NetAgent 9.2.69. Other machines with the same programs in the same sector don't have this problem. I installed the newest version of Skype 6.x. Any ideas?
Your policy settings can be too strict. Skype can be pretty aggressive with it's network behavior, so heuristics can false detect some rogue activity.
Try these steps first: