Starting in Spring '13, Salesforce introduced a change to prevent unintended emails from being sent from sandbox organizations. In order to send email in a sandbox created/refreshed after Spring '13, the Access Level must be changed to All Email. 

Navigate to Setup > Email Administration > Deliverability to update the Access Level to All Email.