Bob Dole carried Colorado in 1996, albeit only by a point, and the state actually trended left in 2000.
For some reason, CO Republicans had a lot of success in state races during the mid-to-late 90s, and Gore performed horribly in the Rockies. It made sense that it would swing left in 2004, when there wasn’t a strong Nader factor, and when Colorado liberals reacted to Bush’s environmental and war policies.
The Denver suburbs were much more Republican back then, and Boulder and Denver, while solidly Democratic by 2000, were not as overwhelmingly so as they are now. El Paso and Douglas Counties were also much more Republican at that time than they are now-Reagan and George H.W. Bush both got over 70% of the vote in El Paso County, and it was one of the few counties in the state to give Bush a majority in 1992. Arapahoe and Jefferson Counties, on their part, did not vote Democratic at all in any election during the period 1968-2004.