I have a work-around and a possible cause, but not a fix. The problem
started for me three weeks ago when I installed SP2 for Exchange 2003
server (I had Exchange 2003 SP1 before). Not only have several of my
users been having the problem in this discussion thread, but a few of
my users are also having problems with their Outlook 2007 rules
working. These problems only seem to be occuring on my Outlook 2007
users, not on my Outlook 2003 users.

The work-around is to uncheck "Use cached Exchange mode". Then both
the Categorize and mail rules work.

I tried deleting the .ost file and having Outlook rebuild it. I also
tried docked and undocked modes on my laptops. I even created a brand-
new AD account and mailbox, and logged this user onto a brand new PC
that I put Office 2007 on (not an upgrade for Office 2003 like my
other users having the problem). Still this user got the error when
doing a categorize. If you check 'Use cached Exchange mode" the
categorize and mail rules work for a few minutes but then stop
working, or work intermittently.

Perhaps with this clue, one of you can help figure out the cause.