This is not an uncommon error message, and it usually indicates that the Mac encounters a network or mail server connection glitch. There was a Microsoft hotfix for this with Exchange Server 2003, and I'm certain it was incorporated into the 2007 release.
If you're getting the error repeatedly it's a good idea to make sure that your Exchange server isn't set to lock you out after a certain number of attempts - I've encountered instances of people complaining about repeated errors when in fact their Exchange Server was simply doing its job and locking them out.
Another cause of the problem can be spam messages with non-roman characters, stuff coming from China, for example. You have to delete the spam before Entourage can login, but do it via Outlook.
In your case it sounds as if neither of these circumstances apply, and I would guess it's the unknown network glitch syndrome at work.