Note that this bug does NOT occur on Debian. Debian now has the same verions as ubuntu:
Ubuntu: evince=2.20.1-0ubuntu1 / libpoppler2=0.6.2-1
Debian: evince=2.20.1-2 / libpoppler2=0.6.2-1
So, either Ubuntu's evince patches have made it impossible to print many PDFs from evince, or it is a problem with another package... perhaps libfontconfig1?
Ubuntu = libfontconfig1=2.4.2-1.2ubuntu4
Debian = libfontconfig1=2.5.0-2