I had this error appear almost on every reboot in my /var/log/mail.err file. Rather frustrating considering reboots are so infrequent that I would forget that dovecot failed to start and troubleshoot anew IMAP access failure. Well last time this happened I decided to fix the root cause and below is the solution. As per dovecot wiki this error can appear on some VPS hosts. Resolving this is relatively easy but it's not obvious, the solution consists of installing NTP - Network Time Protocol daemon which keep your time correct and synchronized and then delaying the execution of dovecot service until ntpd service is loaded. Ubunty/Debian Sollution Install the ntp package: # aptitude update Get:1 http://security.debian.org squeeze/updates Release.gpg [836 B] ... # aptitude install ntp By default dovecot startup script does not require the ntp servicet before it starts, so we must modify it that it waits for the ntp before it starts itself. Edit the /etc/init.d/dovecot ...