The FogBugz Maintenance Service should run every fifteen seconds or so. It performs the steps listed here. If it hasn't run in 45 minutes, you will start getting warnings ("Warning: Some errors have occurred in your FogBugz installation.") in the interface. If it runs into trouble, you'll get warnings in the interface.
To check notification emails, look at the Admin > Site > Mail tab. (This is Settings > Site > Mail in FogBugz 6.) It should show you pending messages. If the number is only going up, then your maintenance service is probably not running correctly.
If the number is going down regularly, then FogBugz's outgoing emails are being accepted for delivery by the SMTP server, but somehow not reaching their destination.
The way we usually troubleshoot this is to use FogBugz to notify a variety of addresses and see if they arrive. Here's some steps:
Determine which user(s) has spotty or absent notifications.
Go to Settings > Users and double-check that they have email notifications turned on, then edit that user's email address. Add a comma or semicolon and then an outside email, such as a Gmail, Yahoo, or Hotmail address. It should look something like this:
Create a new case and assign it to that user. NOTE: if this user is you, you'll need to get someone else to create a case and assign it to you. FogBugz doesn't notify you of actions you take yourself.
Get a cup of coffee. Go to Settings > Site > Mail and refresh until the number of pending messages goes down to zero. If this number doesn't change, your FogBugz Maintenance Service might not be running. If that's the case, let us know and we'll send along a different set of steps.
Check your outside mail account. If the notification is there, then there's something happening between the message leaving FogBugz and arriving in your user's mailbox. If the notification is not there, and the pending message count is zero, let us know.