I agree, as you told another individual, that this has nothing do with permissions. However, KB article Q222224 does not help with this issue. He has run a detect and repair. After completion he received: "The messaging interface has returned an unknown error. If the problem persists, restart Outlook."
When using the "Rules Wizard," he does not receive any errors in setup, completion or upon running the rule.
One other thing to consider is that there's a limit imposed by Exchange of about 32K for rules per user. The actual number of rules you can create depends on the length of the rules. If that user already has a lot of rules, this error message may actually mean that they are out of space.
This was first published in October 2002