From my experience this works..

With sql serveragent properties, uncheck the Enable mail profile box.

Stop and restart sqlserveragent

Now Check the Enable mail profile box

Stop and restart sqlserveragent.