If you are using 2004 I would not be surprised, even more so with there "update". I have so many problems even with hotmail accounts!! Anyway, if all else fails, I would copy the emails you want to a new folder and delete the account in Entourage and recreate it, assuming you have it set up as a POP account, if not, if it's setup up as IMAP, just delete it from Entourage and recreate.
Hope that helps