What you are seeing is color (or chroma) noise, which is a manifestation of read noise. I wouldn't call it "very low frequency noise", as it doesn't really have to do with frequency per-se. It has everything to do with image signal strength, however.
The reason noise in the deep shadows picks up inaccurate color is due to the fact that most camera sensors use a bayer design, which makes use of a color filter array. Each pixel is only sensitive to one color of light: red, green, or blue. Additionally, in the deep shadows, the image signal strength is very low, close to the read noise signal strength. Read noise is partially random and partially patterned, and intrudes into the deep shadows in a rather blotchy, sometimes even cross-hatched manner. When you lift the shadows by a significant amount, your lifting everything that exists in the shadows...and that includes read noise.
This is normal with digital image sensors. Generally speaking, you won't be able to lift shadows more than a stop or two before read noise and color blotchieness begins to reveal itself. There is one camera on the market that has better performance in this area: The Nikon D800. It has a wider dynamic range than most cameras, by at least a stop, and in some cases by as much as two stops. The D800, at ISO 100, is capable of being lifted several stops before read noise even begins to exhibit, and a couple more stops before it becomes problematic. The Nikon D600 also has wide dynamic range, however with its smaller pixels, it may not be capable of being lifted quite as much as the D800.
It should be noted that, particularly on Canon cameras, read noise is mitigated somewhat by increasing ISO. Canon cameras tend to have more read noise at low ISO, however they have roughly the same dynamic range at ISO 100, 200, and 400. Since read noise on a Canon sensor drops as ISO is increased, you can actually sometimes get slightly better performance in the shadows at ISO 400 than at ISO 100 (depends on how much actual DR your scene has, and whether you'll end up clipping highlights at a higher ISO). The differences are not huge, but Canon's CDS (correlated double sampling) technology is actually superior at higher ISO, resulting in slightly cleaner shadows, until you get past ISO 1600 (when an alternative method of increasing ISO is used, which results in noise that is just as bad as any camera.)