Try the latest beta version of Skype, 18.104.22.168. 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.
Please note: I do not respond to requests for help via Private Message.