Before joining the Army a few months ago I was training at sea level. My camp is now about 800m above sea level. In the first week I ran 9 mins 40 secs (for 2.4km) and would be out of breath and then after about 3 weeks I was running 8 mins 35 secs and it my legs were the weak point, I still had plenty of breath.I would imagine that you being winded has to do with the fact that you moved from somewhere that's essentially sea-level to somewhere that's 500x higher. Being a native Floridian the first time I went to Colorado the elevation, along with the blizzard(what a great first time to see snow..), made me pretty sick. I still don't do very well at higher elevations so I do my best to avoid mountains at all times, because aside from the elevation it takes forever to get where you're going because there are never straight roads!