Hello,
Here are a couple of things to check for:
What driver are you using to create the PS file from pagemaker? Is it the adobe postscript driver or one for your printer. Usually the adobe drive will give a better PS file and then you get a better PDF.
Also, check the links manager. Is the link for the graphics broken or is the orginal image missing? This could cause this problem.
Good Luck!