Eles são garfos: costumavam ser o mesmo, mas alguém decidiu seguir outra direção. Poppler-utils é o preferido. O Debian já removeu o xpdf-utils da base de código. De bug do Ubuntu # 697119 e erro debian # 622343 eles também estão em conflito uns com os outros devido ao compartilhamento dos mesmos nomes de arquivos.
xpdf-utils parece ser melhor em algumas coisas, mas a partir do link 2: "Esses pequenos erros de regressão devem ser submetidos ao poppler (de preferência popper upstream), onde eles podem ser consertados".
O Poppler é usado no Gimp e no Evince, então essa parece ser sua melhor aposta.