Try the latest beta version of Skype, 188.8.131.52. You can download the installer via this link: www.skype.com/go/getskype-beta
If the problem persists, can you try connecting that PC via Ethernet instead of wifi?
You can also click in Call > Call Technical Info while you're on a video call. Copy and paste the info here which may shed some light on where the problem lies.