IOhannes, thank you! So it was two completely different causes, even though resulting in the same error message.
On the Raspberry Pi, I was indeed merely missing the gem-plugin-* packages. It's working there now.
About the Laptop:
Gem-0.87 was released in 2002, and did not have any "movie decoding backends" at all. also, i don't see it as available via deken.
I only got the version number from the README, deken itself shows it as "Gem-v0.0.extended".
anyhow, i don't think there is merit in making Gem available via deken on Linux platforms at all. deken is not meant for this kind of packages (that have zillions of dependencies). install Gem via your system's package manager. if there is no package for your specific distribution, nudge someone into it. or get involved. or use a Debian derived distro.
Ok, I hear you and will not try deken for Gem again. I'm going to see if I can package Gem for Arch.
Carlos