Not connecting to SQL Server over VPN
On a default instance, SQL Server listens on TCP/1433 by default. This can be changed. On a named instance, unless configured differently, SQL Server listens on a dynamic TCP port. What that means is should SQL Server discover that the port is in use, it will pick another TCP port. How clients usually find the right port in the case of a named instance is by talking to the SQL Server Listener Service/SQL Browser. That listens on UDP/1434 and cannot be changed. If you have a named instance, you can configure a static port and if you have a need to use Kerberos authentication/delegation, you should.
What you'll need to determine is what port your SQL Server is listening on. Then you'll need to get with your networking/security folks to determine if they allow communication to that port via VPN. If they are, as indicated, check your firewall settings. Some systems have multiple firewalls (my laptop is an example). If so, you'll need to check all the firewalls on your system.
If all of those are correct, verify the server doesn't have an IPSEC policy that restricts access to the SQL Server port via IP address. That also could result in you being blocked.
I also had this problem when trying to connect remotely via the Hamachi VPN. I had tried everything available on the internet (including this post) and it still did not work. Note that everything worked fine when the same database was installed on a machine on my local network. Finally I was able to achieve success using the following fix: on the remote machine, enable the IP address on the TCP/IP protocol, like so:
On the remote machine, start SQL Server Configuration Manager, expand SQL Server Network Configuration, select "Protocols for SQLEXPRESS" (or "MSSQLSERVER"), right-click on TCP/IP, on the resulting dialog box go to the IP Addresses tab, and make sure the "IP1" element is Active=Yes and Enabled=Yes. Make note of the IP address (for me it wasn't necessary to modify these). Then stop and start the SQL Server Services. After that, ensure that the firewall on the remote machine is either disabled, or an exception is allowed for port 1433 that includes both the local subnet and the subnet for the address noted in the previous dialog box. On your local machine you should be able to connect by setting the server name to 192.168.1.22\SQLEXPRESS (or [ip address of remote machine]\[SQL server instance name]).
Hope that helps.
Make sure SQL Server is enabled for TCP/IP (someone may have disabled it)?
This will also help you to check/verify the port number the SQL instance is using (in case someone changed it from the default of port 1433).
Obviously port 1433 (or whatever port SQL is listening on) needs to be unblocked by any firewalls between your machine and the box SQL is running on.
To check SQL's network configuration (requires SQL Server Client Tools installed): Start -> Programs -> SQL Server 200x -> Configuration Tools -> SQL Server Configuration Manager
Connect to the machine you need then expand the Tree Item (LHS) "SQL Server Network Configuration", then pick instance. You should have four options - Shared Memory, Named Pipes, TCP/IP and VIA. You can check that TCP/IP is enabled in the RHS window.
If you double click TCP/IP and hit the "Advanced" tab, you can also view the Port number.
Other thoughts.. Are you using SQL Authentication or Windows (Domain) authentication?
If SQL Authentication (which I assume you are using given you said username and password), are you sure the SQL instance you're connecting to has mixed mode authentication enabled? If not, you have to connect as Administrator and change the default security settings to allow SQL authentication.
If Windows Authentication, could your network be using Kerberos potentially? One would think the VPN credentials would be used for the handshake. I'd check your account has appropriate login rights.
When this happens to me, it is because DNS is not working properly. Try using the IP address instead of the server name in the SQL Server login.