Really odd, looks like some compression or (more likely) color indexing is going on there. It shouldn't be doing that... I just tried saving a VERY colorful image as a PDF in Photoshop and it worked just fine.
Is it perhaps the PDF reader you're using rendering it improperly? How big is the source PSD and PDF? If it's small enough I could try opening it to see what result I get.
EDIT: nevermind, just saw the size, and holy shit that's a huge PDF. What resolution is this thing?