Connection problem on Skype

[Anguish]

When I'm in a call on Skype, I randomly get connection failures and the call automaticly closes and the contact goes offline for 5-10 seconds without my network connection to change. 
These "close-downs" can come on random bases.
I have tried turning off my firewall aswell as my antivirus but it doesnt change anything. 

What do I do now...?

[Claudius Community Manager]

Which connection is your contact on? Are you both using the latest Skype from www.skype.com/go/download

[Anguish]

We both went to Help -> Check for updates and updated the latest one but it didnt change a thing..