Thanks for your help kurkosdr.
I went into VLC video settings and unchecked the
'Accelerated video output' box and also the
'Use Hardware YUV->RGB conversions' box.
This has worked a treat and they are all playing great.
The always helpful safe mode! Glad it worked for you.
What's the model of your graphics card?
I had a similar problem with the "Hardware YUV->RGB conversions" with a laptop with an ATI mobility X1600 video card. It converted to RGB 16-235 instead of the proper RG B0-255. As a result, the color range was compressed, the colors where not as vivid, and the black was in fact grey. To be precise 6% grey! Both with new and old drivers. Disabling the hardware YUY->RGB conversions solved it for me too.
Anyway try upgrading your drivers, it may work for you, and you might be able to enable accelaration again (altough the hardware YUY->RGB conversions are not as useful, accelaration is very usefull as it takes off cpu load). I never had a problem with the video accelaration on any Nvidia or ATI card with vlc, so if it's the hardware accelaration causing it, it will be kind of weird. Leave the hardware conversions off and enable the accelaration, and see if you have the problem again.