Well, yeah, they didn't appear insanely red, they probably appeared quite natural like they do in the corrected picture I posted (well, at least natural for someone who just spent some time shooting a film in Tunisia).
There was no magic involved, the overexposure just made the camera brighten and blue/cyan shift the whole image, which is the only thing I tweaked about it (oh, and I turned saturation down a bit).