It should work, so it's a poppler bug.

Here is another PDF file that is not correctly converted to PS. 

http://www.boardgamegeek.com/file/12795/playeraid%20front.pdf

Reported here: 

http://bugzilla.gnome.org/show_bug.cgi?id=416303

Created attachment 9103 [details]
Another PDF that is not correctly exported to PS

Here is another PDF, in this case the resulting PS document is completely empty.

The original ("u2.pdf") file is still broken.
GSview 4.8 2006-02-25
play_sound: not implemented
debug=0
Unknown in Comments section at line 4:
  %%DocumentSuppliedResources: (atend)

Unknown in Prolog section at line 14:
  %%Copyright: Copyright 1996-2004 Glyph & Cog, LLC

Unknown in Trailer section at line 6122:
  %%DocumentSuppliedResources:

Unknown in Trailer section at line 6123:
  %%+ font T3_83_0

Unknown in Trailer section at line 6124:
  %%+ font T3_8_0

Unknown in Trailer section at line 6125:
  %%+ font IQOCZL+MinionPro-Capt

Unknown in Trailer section at line 6126:
  %%+ font AUWEAN+MinionPro-ItCapt

Unknown in Trailer section at line 6127:
  %%+ font PYRERR+MinionPro-It

Unknown in Trailer section at line 6128:
  %%+ font T3_62_0

Unknown in Trailer section at line 6129:
  %%+ font T3_58_0

Unknown in Trailer section at line 6130:
  %%+ font T3_60_0

Unknown in Trailer section at line 6131:
  %%+ font T3_71_0

Unknown in Trailer section at line 6132:
  %%+ font LVRBOX+MinionPro-Regular

Unknown in Trailer section at line 6133:
  %%+ font XYORBH+MinionPro-Regular

Unknown in Trailer section at line 6134:
  %%+ font HCTTIP+MinionPro-Semibold

Unknown in Trailer section at line 6135:
  %%+ font UHHTBH+MinionPro-Subh

Unknown in Trailer section at line 6136:
  %%+ font AHVKWZ+CMSS12

Unknown in Trailer section at line 6137:
  %%+ font T3_39_0

Unknown in Trailer section at line 6138:
  %%+ font T3_21_0

ESP Ghostscript 815.04 (2007-03-14)
Copyright (C) 2004 artofcode LLC, Benicia, CA.  All rights reserved.
This software comes with NO WARRANTY: see the file PUBLIC for details.
Displaying DSC file /home/bradh/devel/poppler-group/poppler/utils/u2.ps
Displaying page 1
WM_GSTEXTINDEX not implemented
ERROR: /undefined in ImData_40_0
Operand stack:
   (A)   43.5
Execution stack:
   %interp_exit   .runexec2   --nostringval--   --nostringval--   --nostringval--   2   %stopped_push   --nostringval--   --nostringval--   false   1   %stopped_push   1   3   %oparray_pop   1   3   %oparray_pop   1   3   %oparray_pop   1   3   %oparray_pop   .runexec2   --nostringval--   --nostringval--   --nostringval--   2   %stopped_push   --nostringval--   --nostringval--   %finish_stringwidth   --nostringval--   --nostringval--   9   8   2   --nostringval--   (gs_show_enum)   %op_show_continue   --nostringval--
Dictionary stack:
   --dict:1120/1686(ro)(G)--   --dict:0/20(G)--   --dict:107/200(L)--   --dict:65/75(L)--   --dict:18/24(L)--   --dict:0/15(L)--   --dict:8/15(L)--   --dict:2/15(L)--   --dict:0/15(L)--   --dict:0/15(L)--
Current allocation mode is local
Last OS error: 2

--- Begin offending input ---

--- End offending input ---
file offset = 173375
gsapi_run_string_continue returns -101

The file in comment #2 works fine with head.

The file in comment #3 (the attachment of 2007-03-12) also works fine with head.

All pdf these seem to export to ps correctly for me, please reopen if they still fail for you.