As of Sept, the FAA has proposed that RVSM begin in earnest within the continental US sometime during 2004. The military has been granted an exemption from the rules in that they will not be compliant by that point (making aircraft compliant with RVSM requirements necessitates a major upgrade in the air data computing systems and routine maintenance/calibration).
The reason 2000 ft altitude separation is needed is due to the non-linear decrease in air pressure at higher altitudes. The change in air pressure from, say, FL 290 to 300 is far less than the pressure change you get when moving from 5 to 6 thousand feet. Without upgrades, older altitude measuring systems are not sensitive enough to accurately maintain altitude at the higher flight levels.