I live at 7500' elevation, routinely drive over 9000' on my 100-mile round trip commute, and often over 10k'.
I use opti-lube summer and winter in their respective seasons to their minimum dosage. I tried doubling the dose only waste money. I notice a 1.5-2 mpg gain using the additives.
I put 70K on a 2002 NB, S7, PP520's, and perfectly timed/modified by Anut at Dieselland. (347K when I sold it) It routinely returned 48 mpg winter and 52 mpg summer. This is driving without concern for mileage, passing when I wanted, using the AC, etc.
I put 50K on a 2003 Jetta Wagon, completely stock with 277K on original clutch, injectors, etc. Routinely returned 48 mpg summer and 45 winter with skybox mounted on top in the winter to hold skis. Again, driving without care for mpg. I timed this one which could be the problem.
I am "from" South Dakota, and when I drove those cars back there (~1300' elev.) I did not notice a jump in mpg at all. What I did notice is that my glow-plugs would only cycle just a few seconds even on a cold engine and the thing would fire right up. Much longer glow up here in CO.
I buy my diesel at City Market/King Soopers, as I like the $1.00/gallon savings on 35 gallons and we all have to eat! I read about it, but cannot remember their cetane rating, but I believe they just get the leftovers of the local supplier without a proprietary blend of additives.
Sorry for your huge hit in MPG. I do not think elevation is to blame, although I am one of the more dull knives.