GregB, for what it is worth, I use Acrobat Pro v9 on a Mac, with no issues with this command. Have you tried converting to a different CMYK profile and or say an RGB or Gray profile just to double check?
Use the Output Preview / Object Inspector to click on the object and double check the image properties (not the default Output Preview / Separations option).
Have you tried - Advanced / Print Production / Convert Colours? Does this work?
Under the "Matching Criteria" you can select "image", the source colour space, and the profile in the "Conversion Attributes" section (the more matching criteria in use the better, as this is a global image conversion command, it is not targeted like the touch up object tool). You can also isolate the change to all the images on a certain page using the "Convert Pages" section. For good form, it is a good practice to also tick the Convert Options conversion boxes for Preserve Black and Preserve CMYK Primaries.
Is the original image "Device CMYK" - or does it have a tagged ICC profile associated with the image? You can find this out using the Object Inspector tool.
If the image is Device CMYK, what CMYK device profile is set in your Preferences / Colour Settings?
Regards,
Stephen Marsh