My 1997 Excella never had an issue running the furnace above 6,000 feet and up to 8,000 (never ran it higher than this). But I did find an interesting quirk with starting that drove me nuts till I realized why sometimes it wouldn't fully start (similar to your symptoms). Disclaimer, I really don't know if this is a design built in or just a fluke of my 97 Excella, and it did this every year for 16 years). When testing heater out before taking trips, if my inside AS temperature was pretty warm the heater would go through its staring fits and never stay lit. If I waited till the evening, thus cool outside and inside, it would fire up and stay lit. I don't know, but I am not making this one up. I take delivery next week of my 2016 25 FC, I hope it works above 6,000 feet because in two weeks that will be my lowest altitude for 4 weeks. Good luck!
2016 RAM 2500 6.7L Cummins, 4WD, Crew, Rear Air