From the trusty ghostscript package, I ran ps2pdf and got a PDF file. Trouble was, the graphics had been JPEG'd -- boy were they ugly! Asking my colleagues (I love this company!) yielded this answer:
ps2pdf -dAutoFilterColorImages=false -dColorImageFilter=/FlateEncode x.ps x.pdfThat was it. Other possibilities exist but I recently re-used this one and it works great.
For some reason, if we have just text it seems to be OK. Maybe if it detects grays it tries to JPEG-ify them? Anyway, I wanted to put this incantation where I could find it easily later -- and now you can too :)