Hello,
die genannten Tips hatten bei mir nicht zu gewünschten Ergebnis geführt.
Bin dann aber durch Zufall drauf gestoßen, und evtl hilft es anderen ja auch 
Wenn man Threema z.B. aus Titanium Backup restored hat, ist die Push-Registrierung der APP beim GCM-Dienst nicht korrekt.
Dieser arbeitet mit Tokens, d.h. wenn man aus einem Backup wiederherstellt, wird auch ein alter, ungültiger Token verwendet.
Lösung ist: die APK nochmal "drüber installieren", dabei wird die GCM-Registrierung wiederholt.
In Kombination mit den bereits gennanten Tips funktioniert es nun endlich bei mir.
