Finally found the answer here:
The upgrade package left some stuff around that is now obsolete and no longer works. I upgraded directly 8.04 -> 9.10, skipping the intermediate releases (won't do that again. Why didn't adept notifier tell me that?)
Do NOT simply delete /sbin/lrm-video as the page above suggests, however. It doesn't work.