Nowadays, most VPN software has a built in statefull firewall that kicks in when ever the tunnel is activated. The symptom you mention that the PC has to be rebooted makes me think that even when the tunnel has been shut down the VPN software is still open and the firewall service is still active. To be able to connect to the PC you should make sure that the VPN software is fully deactivated. A basic test if there is an icon in systray then the software is still active. The definitive way though is to stop related VPN services, or reboot.
If the PC user cannot disable the firewall then you will need to contact the client's helpdesk.
As a side note....I had a similar experience with the Cisco VPN client. Upgrading this to the latest version fixed the issue.
Regards