I had the same problem too (with a chip I wrote myself so I know that wasn't the problem.
It turns out that it's the TV not the PSX that doesn't support the NTSC (No Two Same Colours) colour encoding. Get a new TV (erm...kerching!) or, like Donk says, get a scart cable!
Hope this helps!