I have a similar problem with my '09 XBOX 360 elite.
Sometimes, when it starts up, the boot animation and, from there on out, the video in general is black and white.
When I go to the video settings and change it to PAL-50, I have color again.
This is weird, because I always run my 360 in PAL-60, so I know my TV can handle it.
Sometimes it goes back to displaying colors in PAL-60 after a couple of switches between PAL-50 and PAL-60.
And otherwise, setting the console to PAL-50 and then rebooting, and setting the console back to PAL-60 seems to help as well, maybe you should try that too.