Salesforce Spring '13 introduced a new email deliverability setting (Setup > Email Administration > Deliverability). New sandboxes I believe are automatically set to "System email only," causing this error.
If this doesn't work, try calling the code synchronously.