Created attachment 57916 [details]
PS testcase

Yeah, this document is broken. It should start with 

%!PS-Adobe-3.0

If you remove top two lines, everything will start work nice. I suspect, it's better to find the reason of this bug first. But it's possible to create workaround probably.

This document was produced by redirecting cups output to file

Created attachment 104011 [details]
testcase 2

Another postscript for which page count is wrong in evince but right in GV.

I would like to report a variant of this problem. The postscript file generated
by the ArXiV service for the paper http://fr.arxiv.org/ps/0801.4031 is
apparently incorrectly  opened by evince. It says that it contains 2 pages.
However opening this same file with GV indicates that it contains 5 pages (the
true number). I have attached a compressed version of this postscript file to
the bug report.

(In reply to comment #4)
> Created an attachment (id=104011) [edit]
> testcase 2
> 
> Another postscript for which page count is wrong in evince but right in GV.
> 

This works for me with current evince compiled with libspectre and even faster than GV. 

Created attachment 112274 [details]
Example document with pages in the wrong order

I'm not sure if this is the same bug, but evince displays the pages of this document in the wrong order, while gv gets it right. The document itself seems to be correct.

No, it's another bug that I have just fixed in libspectre. Closing this bug since it seems that both issues are fixed now. 

Thanks for reporting.