Andrew,

When I lived in Wyoming 95-99 (next door to Vidavoo/Kurt Goudy State
Park) my house was at the 7,500 level.  My O2 sensor (90 GL) fail just
as if it was at sea level, a slow degredation over time.  Two ways to by
pass the O2 sensor: 1) turn the key off and back on quickly this resets
the computer; 2) floor it, this by passes the logic (in a way).  So I
would say if you are driving with it floored and the problem still
exists I would not suspect the O2 sensor as the first problem.

One thing that did require fixing when I moved to Wyoming was the wiring
harness adapter to the Air Flow Box.  Being higher and colder...thus
dryer...static electricity in my van built up extremely fast... Thus the
harness fix (PS my van runs fine with out the fix at sea level).

Raciung Heuristic: plugs = low speed failure; timing/rotor/etc = high
speed failure

Check the boot from the air flow box to see if the back side is secure
and not letting more air in.

From there... Back to the basics... Filters, compression, etc...

Jere