A few things to check:-
1) Can you Ping the Server from the Client?
2) Can you Login locally to the SQL Server using the User/Password combination?
3) Are there any relevant login failure messages in the SQL Server Logs? This would indicate an authentication issue, rather than a network connection problem.
Finally can you post the full error message including Error Number, Level and State?
SQL Server Luxembourg User Group