I fixed this problem simply by installing xpdf-utils (which removes poppler-utils). I don't think the dependency problem is a red herring.