This is a pretty generic message and hard to troubleshoot without more information.  When I've seen it in our place it was with a Sybase app and it's always been client installation or configuration issues.  For whatever reason, the client can't talk to the DB which can mean anything from a missing dll to to the server or DB being off-line.

Can you ping the server from the clients or set up an ODBC connection?  Are your event logs reporting an error when you attempt the connection?  If so, they might point you in the right direction.