Are you by any chance on a Mac running either Lion 10.7.x or Mountain Lion 10.8.x?
Are you running Photoshop CS6 or CC?
If the answer to both questions is yes, then it may be related to this anomaly, also involving a CMYK PDF:
Next time, don't forget to indicate your platform, the exact version of Photoshop and the OS, and anything else about your machine and setup, as well as how the image was generated on your client's side.
I'm running Snow Leopard and CS 5.
Clinet used ID, but I don't know what version.