pdf2ps -sDEVICE=psgray original.odf ps2pdf original.ps new.pdf
This works, but this has the unpleasant side effect to increase the size of the PDF and to lower the quality (for a reason which escapes me). So I looked again in the magic pdfwrite parameters, and I came up with the following solution, which works on my box (though the above page suggests it shouldn't):
gs -sOutputFile=biniou.pdf -sDEVICE=pdfwrite \ -sColorConversionStrategy=Gray -dProcessColorModel=/DeviceGray \ -dCompatibilityLevel=1.4 Plot.pdf < /dev/null
This works fine, does not lower the quality of the produced PDF and in the case I tried even made it smaller...