This strikes me as a name resolution problem, but we'll have to go through a few steps to isolate it.
Have a user connect to the VPN, and try to manually map a drive to the shared folder that contains their profiles. Make sure you connect using the exact path listed for their profile in their user account settings. If this fails, then you've narrowed down the problem a bit.
Can you connect to the shared folder using the server's IP address? For example, if the name of the server is "server" and the server's IP address is "10.10.10.10," and you have their profile listed as \\server\profile\username, try connecting to \\10.10.10.10\profile\username. If this succeeds, then you have a name resolution problem. Verify that the clients have received the proper WINS/DNS server settings, and continue to troubleshoot the problem as a name resolution issue. If it still fails, then the clients are having a general problem communicating with the server, and you should continue to troubleshoot the problem as a network connectivity issue.
Good luck -- hope that helps.
This was first published in March 2003