We have been seeing this happening for a decent chunk of our users forever as well...
When we try to get an InstanceID token for GCM, around 0.2% of our user base is getting this error. This happens to people with a variety of devices and Android versions, and not only to people with rooted devices.
Here is the code that triggers it:
InstanceID iid = InstanceID.getInstance(getContext());
final String token = iid.getToken(AppConfig.GCM_SENDER_ID, GoogleCloudMessaging.INSTANCE_ID_SCOPE, null);
And here is the exception:
java.io.IOException: PHONE_REGISTRATION_ERROR
at com.google.android.gms.iid.zzc.zzb(Unknown Source)
at com.google.android.gms.iid.zzc.zza(Unknown Source)
at com.google.android.gms.iid.InstanceID.zzc(Unknown Source)
at com.google.android.gms.iid.InstanceID.getToken(Unknown Source)
at my.package.GcmUtils.registerWithGcm(GcmUtils.java:35)
Here is some kind of distribution of people it's happening to in Crashlytics:


I wish I could provide more information but this is all I have...
Hope that helps and there is a way around it, we are running a messaging app and we can't afford that many people from not getting notifications, otherwise we will have to implement our own infrastructure for push messages...
Thanks!
Nathan