Discussion: Density

Although density does change, it's not by all that much. Between 70F and 30F, it's nominally about 8% (equivalent to changing your altitude by 2200 feet), although there are some other factors like the humidity changing. This comes up in hang gliding forums all the time, with people thinking that colder air at a given wind speed will have twice the effect or some such. Maybe 8% is in the range of what you're experiencing, though. Don't forget to account for the air in your tires contracting -- if you aren't actively pumping them up on cold days, they might be soft, and that will also slow you down.

(Somebody might want to check my math...)

People at least used to attempt to set the hour record in cycling at velodromes in or near Mexico City, i.e. at a fairly high though not, by mountaineering standards, extreme altitude. Presumably they knew what they were doing and thinner air is a net advantage up to some crossover point where you can't get enough oxygen to take advantage of the lower drag no matter how awesome your lungs, etc. are.