This issue can happen for many reasons:
1. The Email server is down, or the server is not allowing your SharePoint server to send emails. Check each SharePoint Server in the farm individually.
2. Check if your Windows SharePoint Services Timer service is running. To start it go to my article: http://blogs.tamtam.nl/duarte/2008/12/19/SharePoint2007TimerJobsNotWorking.aspx
If these don't help, let me know what was your problem & solution in the comments below! :)