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