I'm currently using everything you state there except for Pitstop. Mac OS 10.3.4, Nexus 7.5rev4 and Acrobat 6.1. We don't use Pitstop much anymore, our version is a bit old and was always a bit flakey.
In similar occassions, we try one of these.
1) Simply leave the CMYK images as is and run it using the printer feature of Composite-Monochrome. That usally works, of course you are a slave to what Nexus thinks the conversion should be.
2) Set the Acrobat feature under Advanced to make all greyscale and still using the Composite-Monochrome, or once in awhile Composite-BlackOnly. Again, not much you can do for setting up the conversion.
3) We use the Acrobat plugin Quite A Box of Tricks (
http://www.quite.com/) for convert to "grayscale" and "all text to black". This almost always works for us, usually good enough for final product delivery.
4) Print to a vector based workflow, if you have it. You have a large group of options through Nexus Edit to fix things like this.
5) As Kakuzo stated, control+click on the image that you want to convert and edit it through photoshop as a temp file and have it save it back into the pdf itself. We sometimes have issues saving the image back into the pdf, this might just be our setup though, it used to work better.
Hope this helps.