I finally found some time to implement the solution
proposed on the (gnuplot) list here - I wrote a perl script that
can change the colors in the postscript file output
by gnuplot. As this problem arose in an octave context, I am
crossposting it to the [hidden email] list as well.
Hope this will be useful for more people than just me.