Funny, in this document here :http://developer.android.com/google/gcm/adv.html They say that the NotRegistered code will be sent. When I typed in "APNS InvalidRegistration" into google it showed me that that is the error code from Apple. Ergo as far as I can tell we were checking the Apple code from their docs instead of the Google code from their docs.

It isn't my fault Google's docs suck