On a hunch, I used Evince to print the aforementioned PDF as a file to postscript. The LaserJet prints that .ps file just fine. And, fuerther Googling reveals that PDF get converted to postscript when being sent to the printer. So, maybe pdftops is to blame?