I had that exact feeling when I visited denver, many years ago when I was doing triathlons. I woke up the next morning, went to the gym to do a 1 hour bike threshold session, and started panting for breath within the first 10 minutes of warmup. I was like, what-the-heck?

Then I remember Denver was the mile-high city.