Julian, This problem is also affecting me. When I print any document containing images, the quality is very very bad. When I use Acrobat Reader to print the same file, the quality is very good. Is there anyone working on this? I'm using sid/experimental. My poppler-utils version is 0.16.7-2+b1. If you need more information, just ask!
Thanks! Estêvão Samuel Procópio