A última sugestão, na verdade, só converte em escala de cinza e só funciona se o documento subjacente usar setrgbcolor . Isso não funcionou para mim, já que eu tinha um doc, que usava setcolor .
Eu tive sucesso com a redefinição de setcolor para sempre definir a cor para 0,0,0:
gs -o <output-file.pdf> -sDEVICE=pdfwrite \
-c "/osetcolor {/setcolor} bind def /setcolor {pop [0 0 0] osetcolor} def" \
-f <input-file.ps>
Já faz mais de 15 anos que eu fiz qualquer hacking de PostScript, então o que está acima pode ser ruim, incorreto ou até mesmo acidental - se você sabe como fazer melhor, por favor sugira.