Every time I've seen this error, it's been either due to incorrect email settings. Verify your SMTP server (you find this in Process Manager > Admin > Master Settings > Email Settings) is correct, and also verify the settings in Admin > Data > Applications Properties > ServiceDeskSettings, for the SMTPMailServer, as well as the SSL settings, mail server port, mail server, username/password, and protocol.
We ran into a similar issue during our implementation, and as soon as we made sure we were using the right username/password for the POP email monitoring and had configured the right mail server (HAS to allow POP, I think. I'm pretty sure Exchange 2007 doesn't as configured out of the box) we were up and running.