Why are almost all my gradients coming out straight black when I export to pdf and print?

They look fine in ID and Acrobat, even with overprint preview turned on. But when I print the pdf, the majority of the gradient is pure black.
See picture: <http://mversion.com/files/cat_id3_02.jpg>
I export in Acrobat 5 format.

Also, when I print from indesign, I have missing blocks of colour on some shapes and font.

See picture here: <http://mversion.com/files/cat_id3_01.jpg>

I use Indesign CS on WinXP and I am printing to a tektronix phaser 850DP.

I send my publications to our printer as PDF... so the PDF issue is obviously more important.

Any help would be greatly appreciated.