I’ve been setting up a Postfix/Dovecot solution on a linux Fedora 9 machine and ran into this problem.

A little snooping around led to this solution:

Dovecot requires the dovecot-mysql package to run mysql authentication. This problem is simply cured by installing it with yum:

yum install dovecot-mysql