After ruling out any bug/cron issues, it would also be a good idea to check your SMTP settings are right. Go to your site home page and locate the Site Administration block. Click on Server > Email to see your current setting.
Let us know how you get on.
Marty