Alright, I tried my hand at color correcting these bad boys. I tried to make it as simple as possible, so this is the three-step process I did in Photoshop:

1. Adjust the Levels for each shot.
2. Color Balance, adjusting the shifted the Cyan/Red between -30 and -50 and the Yellow/Blue between -15 and -20.
3. Used Selective Color to add Reds back in.

They're not perfect, but I think they might be a good starting point.

In doing this, I found that throwing a blue filter is a really tempting way to fix a film faded like this. I can understand, but not excuse, the 2004 DVD now.