as far as some of moth3r's comments, while some i think are valid, i think your 'over-thinking' some parts of it.
1) agreed the few would imply 3-5 years, but I agree with Rebel11_38 about the term present being 'flexible'
2) they didnt have re-programmed T-800's they had one T-800 that they managed to capture and reprogram to send back to the past. and that wasnt available to them when the first terminator was sent back. Why the covered it the same as the one in the first movie, well a) they didnt necessarily know what the t-800 unit looked like, and you have to assume their access to the robot's arsenal was limited at best, and they had little of their own supplies to use to make coverings for the terminator, so im sure the machines had more than one 'look' for the terminator. plus, most of the time they fought as machines, that was only for infiltration.
3) time machine, do we know that they succeeded in destroying the time travel facility? nope. machines could have defended it. how do the humans know that was the only facility? why couldnt the machines be able to build another one? why couldnt this new facility be more advanced and allow liquid metal terminators to pass through?
4) not that i dont agree that the quiet terminator made a good portrayal of the relentless killer, but remember, reprogrammed. especially after the inhibitor chip was removed.
5) any (well their might be a few exceptions) time travel movie is filled with paradoxes. there are so many interpretations of time travel that its mind boggle to even think about them or what the effects would be. Even though they have the no fate but what we make, that someone said was 'abandoned' in 3. if the Machines didnt send back the terminator, john wouldnt have sent his father back, john wouldnt have been born, and the machines would have had no reason to send a terminator back. same thing with the arm in the factory. I think in the extended (might be the 'hidden' cut, on the T2 disc, not the more recent one, but the Ultimate one i think it was) the ending leaves the future open, never says that judgement day was prevented. (as i think the theatrical ending does) So i think a lot of this is open to interpretation, and the thing is more than one works. You can say that they are changing the future, or you can say that they are only playing their parts in what is bound to happen. thats what 3 seemed to say, but the only real problem is the fact that judgement day was still delayed. which makes the war at the end of 3 different than the war in the first. I think someone mentioned it, but if you remove references to the delayed judgement day, and make it only be the one judgement day it would work. I also think that Rebel11_38's idea for a quadrilogy woul be pretty interesting and have a good flow as well. But like i said, its about interpretation of the timeline (which is the case in any movie that touches on time travel, should see if i can find my time travel thread from a while back) the more sequals/prequals you make on the same idea, the more paradoxes you are bound to introduce, especially with the 'future is set' type timeline.
-Darth Simon