Hi. I was getting the same error for a particular user on Outlook 2003. The problem was only happening for her profile. I could log in and it would work fine. If I created another Outlook profile while logged in as this user, I would still get the same problem.

The way I fixed the problem was to go into the Tools>Options>Spelling Tab, then change the International dictionaries to another language (eg. I changed it to English (UK). I then opened up a new e-mail and did a spell check. This worked without bringing up the error. I then went back and changed the International dictionaries back to it's original language. In my case English (Australia). Then tested it and it worked again. Hope this helps. :-)