Did you create the AI file. I have CS2. When the AI file is saved you have the following options in CS2 (but very simialr in 9, 10, and CS):
Create PDF Compatible File
Incluce Linked Files
Embed ICC Profiles
Use Compression
You must make sure that the file is saved with Create PDF Compatible File and Use Compression UNCHECKED. If you recieved the file from someone ask them to save it again with those options unchecked. It is also good to try and only save the layers you need to reduce the amount of overhead in the sketch.
RFUS