Have you checked that you haven't got Member of no secondary groups selected (you should have Member of any of these secondary groups selected though you don't need to tick any of the groups)? Sounds like this could be the problem if no-one in a secondary group is getting the email.
If this isn't the issue, have you checked that they are not being sent the email? Have you generated a list of email addresses (by ticking Only generate a list of email addresses on the Email Users page) that the message is sent to when you are selecting Registered as the only criteria?
I've just done this and all admins and mods are on the list, so it's working fine on my site.
Also, be aware that users who have opted out of receiving site mailings won't get the email unless you untick the option Only send to users opting to receive emails from the admin.