Starting with Magento 1.9.1 the emails are not being sent directly during checkout but instead are being queued. The queue is being processed via your Magento cronjob - please ensure this has been set up and is running correctly.
The extension AOE_Scheduler can help you in confirming that your Magento cronjob has been configured correctly and is running.
OpenSource Expert | OpenSource Technologies | www.opensourcetechnologies.com
Magento plugins released: http://www.opensourcetechnologies.com/product/product-category/magento-extensions