Very quick answer now, maybe more tomowwrow, if necessary: yep, seems to bee a GCM issue. I assume your WiFi symbol is still grey? And I take it you restored from a backup?
In Threema, there’s an option to renew your GCM-related settings; I thought there would be soemthing like a “renew” option in TextSecure as well - alas, I can’t find it on the fly.
Also, have a look in this thread here, also on how to check if you are connected to GCM.
One workaround might be to restore your android ID from the backup (if your backup solution allows this), since it often changes after a wipe/factory reset, and definetly after a HW change.