Exchange 5.5 Inbox rules...

When creating a new Inbox Rule in Outlook client, the exchange server responds with "There is not enough space on the exchange server to store all of your rules. The rules that failed to upload have been deactivated" Looking at the event log on the server, there is 12 MB available in the exchange db after the last online defrag. There is plenty of space on the drive hosting exchange (many GB). We also receive an error occasionally that reads "This rule could not be created. Check your folder permissions" I have not been able to find anything on Technet, any help would be appreciated!