Hi,
How does the SQL Server Configuration Manager look? Is all configured correctly?
Are you accessing the server using the correct server name from those machines?
When this issue occurs, I would try an odbcping to see what the results would be.
Perhaps you can check into these things until an MVP or MSFT Eng replies.
Good Luck
Frank.
Frank Garcia