Talk about an ambiguous error message! The CUPS docs basically say this could mean anything. Well, this time the fix was actually pretty logical, after turning logging to debug level, /var/log/cups/error_log had this to say:
D [15/Nov/2006:17:19:55 +0200] [Job 8] Unknown device: cdj890
Mmkay, I guess I picked the wrong PPD. Indeed, setting it to “Foomatic/hpijs (recommended)” fixed the problem. Why the initial error couldn't include “Uknown device: cdj890” I will never understand…
Oh, and to be able to use your account on that nice CUPS web-interface, add yourself to the group lpadmin:
$ sudo usermod -G lpadmin filipp