First, log onto the database server and open Enterprise Manager. Under Tools, Options, change the login timeout to something greater than 4. Change it to 30 or more. Often times when the connection settings are valid, the initial connection can take longer than 4 seconds.
Try to connect again from your machine to the DB server using EM.
If it still doesn't work, find out some details about the server you are trying to connect to. What are the required client settings? TCP/IP or Named Pipes? If TCP/IP, is it listening on port 1433 or a different port? Are there multiple instances and are you connecting the right one?
See if you can connect to the DB using telnet on the right port, like 'telnet xxx.xxx.xxx.xxx 1433'.
This is a good place to start. Let me know if it worked out for you.