I had a similar problem last week. If your SQL Server is up and running with no errors, the client issue is most likely due to some kind of network communication problem. Have these clients connected before and now have stopped? If so, you'll need to see if anything like a different version of MDAC or something similar got loaded on them. Can you ping the SQL server or create ODBC connections from the clients?
In my case, I got the error when attempting to resolve an SQL connection using the server name, but did not get it when using the server IP address. Investigation revealed that DNS was not correctly configured on the client therefore it couldn't resolve the host name. Once this was fixed, the application could connect with no problems. I hope this helps you.
My hovercraft is full of eels.