I just had the same problem.
I had to enable DatabaseMail on the SQL Server Agent -> properties -> Alert System (check the checkbox), and then restart SQL Server Agent.
It works now, thanks to a posting by "Johnny" in microsoft.public.sqlserver.server with the topic "How to setup Operator for sending alerts?"
HIH
Henrik Staun Poulsen