To change the colour of a vector image in the GIMP is straight forward enough. I don't know off the top of my head which image formats the GIMP supports and you may need Ghostwriter installed to create PDFs with the GIMP. Basically open your image in the GIMP select the vector elements you wish to change and select the colour you require from the colour pallete. Save file as PDF for your printer and for ease of use as an EPS for possible use elsewhere. (EPS - electronic postscipt - is used as a standard file format across multiple platforms ie is the ultimate "compatible" format).
However, you will need the image in a supported file format and as a vector graphic first (ie illustrator, quark, PDF, EPS there are probably more but they're are the standards used by printers in the UK).
To be perfectly honest if your file is a vector image and of a standard format it would take two minutes for the printers to change the colours to shades of grey.
What is a vector graphic? Think of it as a potentially curved line that can expand or contract in relation to a whole without degrading in "quality".
Four colour process in printing is where all colours are printable and are achieved by combining C-cyan, M-magenta, Y-yellow, and K-I don't know but it's black. Black and white printing is really grey shade printing.
If the image is in the following formats (PDF, AI, EPS) I can make the necessary adjustments, however, if it is available to you as a PDF already you can make the changes very simply with the GIMP (a fantastic program by the way).
Hope that's some help.