The only things that fix the issue is rebooting the server, restarting the SQL service or going into Amazing Utilities and hitting "Repair connections". After one of those actions is done then people are able to connect again.
I have found that keeping Amazing Utilities "live" on the main computer, and hitting the "Repair Connections" when clients can't find the database is the fastest.
I also find it interesting that at the same time that client computers are seeing the error message, other, already logged in clients are accessing the database without interruption. However, if a client logs out and then back in -- error box. This must mean something to a SQL expert.
