I have A.Reader v5.0 and printing on a Xerox Phaser 6200DP. As above, I too am having the same (disappointing) outcome attempting to do this.
Xerox have a KB article about this issue on their Support site.
<http://www.xerox.com/office/out98kb/,case=51462>
It recommends having at least ver. A.Reader 4.0 installed and to select the collating option from the driver properties window before using file/print to produce the document.
I called Xerox support and after running through some checks (the above procedure again, drivers versions, printer HD space and configurations), they too believe the problem is with Adobe Reader especially since the output can be collated in Word etc.
A rare win for MS maybe?
So let's go Adobe. You're currently advertising whether it is better to give or receive a PDF. I may now want to give something else.
cheers
Read this one from:
<http://www.adobe.com/support/techdocs/14b32.htm>
Acrobat Products Cannot Collate Multiple Copies
Adobe Acrobat, Acrobat Approval, and Acrobat Reader for Windows cannot collate PDF print jobs, even if other applications can collate multiple copies of a file to a given printer.
If you would like to request that a collating feature be added to future versions of Acrobat products, you can use the Adobe Product Feature Request Form on Adobe's Web site at www.adobe.com/support/feature.html.