Are you using CMAK clients or you have created the VPN connection on each client?
In case you are creating a new connection to VPN..
Start-- Run---type "ncpa.cpl"
Now go to the property of the connection and go to Networking TAB... Now go the TCPIP property.. and go to the DNS Tab.. Make sure that the "Register this connection is checked"..
Along with that you need to make sure that the DNS server is reachable and the VPN connection is on Top of the network binding order.
Thanks
Kumar