The EXECUTE permission was denied on the object 'sp_send_dbmail', database 'msdb', schema 'dbo'

You will get this error when you try to use the msdb.dbo.sp_send_dbmail stored proc and the user that you are using does not have permissions to execute the stored proc.

The user must be a member of the DatabaseMailUserRole in the msdb database. To give the user permission to do so, execute the following:

EXEC msdb.dbo.sp_addrolemember 'DatabaseMailUserRole', 'username here'

NOTE: If the user has not be added to the msdb database, then you will get an error like the following:

Msg 15410, Level 11, State 1, Procedure sp_addrolemember, Line 75
User or role 'username here' does not exist in this database.

To fix this, you can execute the following

use msdb
go
CREATE USER [username here] FOR LOGIN [username here]

You can also use MS SQL Management Studio to add the user to msdb and to the DatabaseMailUserRole in one step if you like the UI. :)