Jack Corbett (5/18/2009)
In addition to what Jonathan is recommending you should also check your anti-virus setting (if you have AV on your SQL Server). By default McAfee blocks Database mail through it's access protection setting, prevent mass mailing worms from sending mail. When this happens you get the error you listed. You need to add database mail (DatabaseMail90.exe) as an exception to the rule.
I would recomend anyone to check their AV is not blocking port 25 as a starting point, as I have spent three weeks wondering why DB MAil would work on five servers, but not on two others. In the end I spotted a message from McAfee in the Application section of Event Viewer saying it had kindly blocked an outgoing email request ;-)