It could be any number of things. The port is blocked for them. The DNS doesn't recognize the name. The IP address is wrong. Wrong password (sql login, which it looks like what you have). Incorrect permissions for the application (I know, the developers said it's perfect, they always do). Permissions on the server. Permissions on the database. No matter how often you hear that everything is configured perfectly, when stuff like this comes up, something is misconfigured, guaranteed.
I'd start with a simple ping. Can you ping the IP address of the server from the client? Next, ping with a port. Here's a decent article on some other steps you could take.