I haven't found a proper solution, or a corresponding bug report yet, but since I was short on time I found a workaround: Use "pdfnup".

Do the following:
1) install "pdfjam" (on Ubuntu it's in the repositories, so do "apt-get install pdfjam")
2) Now download the pdfnup files from kde-apps.org and store the 2 .desktop files in "~/.kde/share/apps/konqueror/servicemenus/".
3) Restart Konqueror
Now you have a new submenu under "Action" when you right-click on a PDF, offering you to create new PDFs with multiple pages per sheet, making you independent of the printer driver.
Worked like a charm for me.