The workflow queries for the source pages, reverses the order of the even pages using PDFtk and then combines and outputs the pages in the correct order.
Requirements: PDFtk is required; however this step could potentially be replaced with a Python script. Unfortunately, building pdftk from either MacPorts or Fink is currently broken so there is a precompiled version here. I only tested it on OS X 10.6.2, so if you use it on other versions, please let me know in the comments if it breaks. I don't believe it will work in 10.5.x.
The Automator workflow can be downloaded from here. And I put up a screenshot of the workflow in Automator. Please feel free to modify, copy, and redistribute the workflow but please share your improvements here.
[crarko adds: I haven't tested this one. The Automator workflow is mirrored here.]

