Is it an older version of Illustrator, like CS2 0r CS3 as if it is it is a linking problem with bitmaps. What I mean here is that in the older versions even after you placed a bitmap, in the save dialogue, you had to link the images to their file locations so that the images were parceled up with fonts when saving. Made that mistake a few times when sending to printers and my boss was not a happy bunny as he thought it made his shop look amateurish. Which was right but I was coming from other software which did not require this. If you saved it as a PDF I think it means that you haven't ticked the box again in the save dialogue to turn on PDF compatibility (I think that is the wording).

In both methods instead of ID try, if you have a copy, Acro Pro or even Adobe Reader and resave the file.