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.