Sprint was FIRST to have 4g
People seem to forget that Sprint was the first carrier to have 4g. Granted it was WiMax and that ended up being the wrong technology to embrace, they had 4g before anyone else. And as others have said, it is a COMPLETE rebuild from the ground up. New back haul is the biggest delay.
Side note, I'm seeing more and more LTE on my galaxy iii every week now in Mn. There is a steady stream of sites popping up!