I had a problem that was very similar to what you have described too and in my case it appeared that it was some interference being caused by the HDMI to VGA convertor I was using. When I connected to a proper HDMI display the problem went away.
I have today done extensive testing using a Model B Rev1, Model B Rev2 (Chinese), Model B Rev2 (UK) and a Model A (UK). I have used 3 different power supplies, an HDMI to VGA Converter with VGA Monitor and an HDMI Monitor only.
My conclusion is that the problem is related to power supply current capability.
Initially when I noticed the problem I was using a Model B Rev 1 with an MW USBUK1 power supply from CPC (it has Farnell branding) rated at 1A and an HDMI to VGA conveter.
With preview only I had no interference but when saving to file as well I had varying degrees of banding.
Changing to an HDMI monitor I had no problem even when saving to file.
I then tested recording to file with daylight, Compact Fluorescent and Incandescent light sources and had no problem provided I had the HDMI monitor connected and not the HDMI to VGA converter.
If I connected the HDMI to VGA conveter the problem came back but disappeared if disconnected whilst recording.
As the problem occurred when the Pi was saving to file I concluded that as the CPU/GPU were busier the Pi was probably drawing more current, and with the HDMI to VGA convertor connected this is even more (around 150mA to 200mA).
This probably explained why there was no problem with an HDMI monitor, which only draws a few milliamps from the HDMI connector.
So, I changed to an RS power supply rated at 1.2A and I had no problem at all, even when the HDMI to VGA convertor was connected.
To check further I then repeated the tests using a Chinese made Model B Rev2, a UK made Model B Rev2 and a UK made Model A.
I used the CPC and RS power supplies and also used an "el-cheapo" that I had bought from Asda which is supposed to be 1A (but most definitely isn't!).
I rather disturbingly discovered that the problem was MUCH worse with the Chinese made Model B Rev2 - to the extent that even the RS 1.2A power supply was unable to solve the problem.
Both of the other power supplies caused the display to blank completely when trying to save to file!
The UK made Model B Rev2 worked perfectly with the RS and CPC supplies when the HDMI to VGA convertor was connected, but not with the Asda supply.
The UK made Model A worked perfectly with ALL the supplies, including the Asda one - not surprising considering the much lower current requirement of the Model A.
So I am fairly confident that a better power supply is needed when using the camera and as the RS 1.2A one worked in all cases (EXCEPT with the Chinese made Model B Rev2) that's the one I shall use.
Note that this is clearly even more true if using an HDMI to VGA convertor that draws power via the HDMI - a problem which has been highlighted in the past as the HDMI supply is not supposed to be supplying that kind of current.
I am also wondering if the Chinese made Model B Rev2 has some dodgy "knock off" regulators which aren't up to to the job?
I'd be interested to see what other poeple find.