I had a user who's Outlook had apparently deleted the Trash folder from the IMAP server improperly. Outlook functioned okay, but any other email client would barf. The mail client would report a "filesystem error" when you tried to access the Trash folder, and wouldn't delete anything. The server would constantly log:

IOERROR: opening /var/spool/cyrus/mail/j/user/john/Trash/cyrus.header: No such file or directory

I'd noticed the log entries a long time ago, but given that his Outlook was still working fine I didn't stress over it. Now that he's switched to Thunderbird, it became a problem.

The fix was simply to run the following on the mail server:

sudo su - 
su - cyrus
/usr/sbin/cyrreconstruct -rf user.john

If you don't use the dot separator, it would look like:

/usr/sbin/cyrreconstruct -rf user/john

It's a quick and easy fix. cyrreconstruct (or simply reconstruct on some systems) will rebuild the user's entire mail database, and can fix many different types of corruption problems.