Ich habe mich mal registriert, um auf meinen Post antworten zu können.
Mit folgendem Workaround hat es jetzt funktioniert:
Threema vor dem Starten des Backups "pinnen", also in der Liste der aktiven Apps oben auf das Schloss drücken.
Dadurch konnte ich ein Backup für den Umzug zum neuen Smartphone erstellen und das Problem hat sich für mich erstmal wieder erledigt.