Half the users can't connect to SQL server?

I'm currently working on a corporate network where we have a SQL server set up for this department. Normally, it works fine, but today, it seems that about half the users can connect to the server, while half the users can't connect. We've tried restarting the server, but the same users who couldn't connect before still can't connect. It's a Microsoft SQL 2005 Server running on Windows Server 2003. If anyone has any ideas, please post them. This is a bit urgent.

What error do users receive when they fail to connect? Have the affected users rebooted overnight? Are they all connecting from the same physical/network location?

The program users are connecting through is an Access ade that connects to the SQL Server as a backend. The error message that shows up says "[DBNETLIB][Connection Open (Connect()).]SQL Server does not exist or access denied." Some of the users have and others have not rebooted. I've personally tried rebooting one of the problem machines multiple times and it still gives the same error. All the machines are in the same office area here, so there shouldn't be a geographical issue.

Take a user who can login successfully on their machine, have him login with his credentials on a problem machine.

This will tell you if its a user specific issue (ie user profile issue) or a machine specific issue.

This somewhat depends on if your users are authenticating to a domain or all local, but either way its a valid test which should yield more information.

That's interesting. I had a different user login on this computer and open up the database. The DB opened successfully, but it took about 5 minutes, even though it opens almost instantly on her machine.

Alright, I'd try backing up the user profile (desktop, favorites, my documents, application data) for a user who cannot access the DB. Then delete the user profile (computer properties>advanced>user profile>settings), and then recreate the user profile - restore desktop, favs, mydocs, but do not restore the application data folder (you just want to have this as a backup in case).

Once thats done, have that user attempt to access the DB again and see if it works. Btw, I obviously don't have a good answer, but these are the quick fix/triage steps I would try to find a workaround quickly.