I've had the same problem. I emailed a Moodle guru about it and this was his reply:
The two usual culprits I have found for this in the past are:
1. Cron not set up correctly - that would mean none of the scheduled tasks are running properly. If you go to Site Admin > Server Scheduled tasks you should be able to tell
2. The smtp for your outgoing emails and messaging not set up correctly - are other messages, such as forum posts being sent out correctly?
3. The other thing to check is that the assignments are not set to use marking workflow - notification will only be sent out when they are released then.
For us it was the fact that Cron had never been set up! I set it up our server using plesk. I ran it which took 40 minutes. Then set cron to run every minute, as recommended.
I did a test run and students now receive email confirmation.
I hope this helps.
