I tend to agree that these problems are a result of subnetting. SMB generally relies on broadcasts to provide browsing information, and broadcasts do not cross subnets (when everything is working correctly).
Make sure that you are running a WINS server, and the clients are configured to poll the WINS server. If a WINS server is not an option, browsing can be accomplished by using a lmhosts file. Not pretty, but it works.
To verify that you are seeing a name resolution issue, open a command prompt on the client.
Type 'net view \\COMPUTERNAME' replacing COMPUTERNAME with the name assinged to the server in question. Should give a list of the shared resources on the server. If an error is reported, name resolution is a possible issue.
Try again, this time 'net view \\xxx.xxx.xxx.xxx' replacing the xxx with the server's IP. Again, this should provide a list of resources on the server. If this works and the computername method does not, pretty well confirms a name resolution issue. If this does not work either, it does not rule out that name resolution issues exist, but it does inidicate that another problem exists as well. Make sure that NetBIOS is running on the VPN connection of both the client and the server, for starters. Check IP addresses. If you have not already done so, try to ping the server by name and by IP to check connectivity.
When reporting errors for further assistance, be as specific as possible. One very important point, 'ping' always works. Might not give the response you want, but don't say 'ping doesn't work'. Report the specific error message, as each of the dozen or so messages can indicate a different problem.