First, make sure you subscribed right. Post a comment and enter your E-Mail address in the form, choose Yes to Notify, and Submit the comment. Then post a new comment after that - the first person should get an email update at the address you typed into the form about the new comment.
If it doesn't work, check your PHP error_log for any details.
If there's nothing there, it may be a problem with PHPSend() function. I run my Joomla site on HostGator, and they have actually disabled PHPSend on their Shared Accounts for security reasons. In Joomla Global Configuration, I had to change the Mail Handler/Method from PHPSend to SMTP - I inserted SMTP details for my webserver, and that fixed it for me. And the notifications are practically instant - I get the e-mail of a new comment 3 seconds after it was written