Is this NTSC or PAL? Make sure you have the correct format selected. If you select, say, PAL and it's an NTSC TV the picture will display in black and white.
I tried both settings, although I am in the UK. Nothing changed. I also tried it in different TVs, in case there was a setting issue there. I am stumped at this point.