VPN over the internet

I have been trying to get a VPN connection to work over the Internet with out any success. I have read the setup instruction as outlined by Microsoft and other sources that I have run across but I am still having problems. When I try to connect to the VPN server I get the response that ?The computer that you are dialing in to does not respond to a network request and to check your server type setting.? I am using NetBEUI for the VPN connection and during the connection process the VPN connectoron the server starts to initialize but the connection is never complete. The connection works when connection from a system on the local network.
Can some one help me with problem? Have I over looked something?