Restore worked fine, but backup was enabled, but not provisioned.
So I started reproducing that error, created logs and finally found that there is an incompatible version mismatch between several components of the gapps package.
In this special case, the GoogleBackupTransport.apk shows version 2.3 whereas other components show version 2.3.3 and 2.3.4 - a colorful mixture...
Some code from the newer packages is calling a service intent of GoogleBackupTransport which does not exist in version 2.3.
Read the full "story" in CM bug tracker, issue 4353 (I'm not allowed yet to post URLs here)
CM Team told me that they are not responsible for gapps - which I understand and respect.
So where could I report such an issue? Who created those packages?
In my special case, I used a newer GoogleBackupTransport.apk from an older Oxygen ROM, based on 2.3.5 - backup is working fine now, I'm happy.
I also considered creating a gapps package based on the 2.3.7 Versions that can be found in the oxygen-rom repositories, but those are not universal packages with all DPI versions, so I won't do that work if that's not a full replacement for the universal package...
Now, how to proceed getting this fixed? Or who could (and likes to) build a universal gapps package based on 2.3.7. A consistent package might solve other maybe yet undiscovered issues as well.
Edit: I'm talking about gapps-gb-20110828-signed.zip, but older versions are affected, too.