new user Register works sometimes

Did you check to see if the emails are going to the spam filters?

So the activation emails are not going to your users’ spam boxes?

It could be your web host. Some hosts do have certain settings which prevent mails from being sent properly. Or, the server could be just busy. This may be the case if this problem has suddenly happened.

Ask your users to check their spam boxes for the activation emails.

If your server does have an issue with the default wordpress mail function, here’s a plugin you could try: http://wordpress.org/extend/plugins/wp-mail-smtp/

Who is your host?