Sometimes the email gets stuck in spam or junk filters.
To get email working, some web hosts require an extra wordpress plugin, such as:
http://wordpress.org/extend/plugins/mail-from/
http://wordpress.org/extend/plugins/wp-mail-smtp/
http://wordpress.org/extend/plugins/configure-smtp/
wp-mail-smtp and configure-smtp can send a test email which often provides useful debug information!
This is a frequently discussed issue here and people have found all three different plugins useful – there may be others.
Please check your host’s knowledge base or faq for further information….