try restarting sql server agent.....if that does not work get rid of the profile and account restart AGENT and then re add everything. I have had the same problem in the past. worked everywhere except on one box,everything was the same, looked it over and over and double checked still did not work.
finally blew it away then recreated and it worked, other have had the same issue after doing some reading.
sometimes its easier to trouble shoot if use the script after you get it set up as well, that s after you have your profile and account set up
@profile_name = 'Your_Profile_goes hear',
@recipients = 'danw@Adventure-Works.com',
@body = 'The stored procedure finished successfully.',
@subject = 'Automated Success Message' ;