It think Paul is right.
We discussed related issues here and here, when resetting/updating, your phone gets issued a new Android ID and Google Cloud Messaging ID (I forgot the correct term and acronym). Either you restore from a backup (TitaniumBackup can do this, I think - at least for the Android ID, this is even prompted on opening after the app after an update) or you re-register your apps by turning off sync and/or messaging capabilities in each app.
HTH. 