Hi mate,
Had this with a load of macbook pros on a network. Our macs were set to the generic printer setting so we changed it to the actual driver for the printer itself and it worked fine.
Just double check that, if not then it'll probably be set to grayscale in printer preferences somewhere.
System Prefs/Print & Fax/Options & Supplies/Driver/Print Using...Select a driver to use