There are some good responses here but also a couple responses of the "the sky is falling" variety regarding the dangers of high altitude diving. It sounds pretty mysterious to the average sea level diver and some adjustment in tables is required, but high altitude diving really is not all that complicated.
When you are diving at altitude you have a few options. You can use a computer designed for high altitude diving that will in effect adjust the NDL and deco requirements for the altitude, you can use the Buhlman high altitude tables (for altitudes from 2301 to 8200 ft), one of the other tables with variable altitude entries, you can use altitude conversions on standard tables, or you can use palm or laptop computers to cut your own tables around actual altitudes, and in some cases travel times and altitdues and time since arriving on site.
When adapting regular tables to high altitude, you need to convert the actual depth at altitude to a theoretical depth. You can do this mathmatically based on how deep you have to go to add another ATA of pressure (since atmospheric pressure is lower at altitude, the depth required to add an additional atmosphere of pressure is less.) or you can do it using a conversion chart which lists various depths on the side, altitudes on the bottom that are used to locate theoretical depths on the chart.
At 3000 feet for example, the theoretical depth for an 80 ft dive would be 89 feet which whould then require you to use a 90 ft depth on the table for the dive rather than 80 ft. and the 90 ft NDL's and RNT's would apply.
You also normally need to account for the ascent from sea level as this is essentially the same as surfacing from a previous dive and results in residual nitrogen time (RNT). Depending on the table and it's rules for high altitude diving, you will normally move over one or more groups for each 1000 ft of ascent and will arrive at altitude with some RNT. And like regular RNT, your group moves back down as your surface interval (SI) increases. In the current PADI tables for example, you go over two repetetive groups for each 1000' of ascent. In the older US Navy tables you move over one group for each 1000 ft.
With a US navy table and a normal get there, say hi, eat lunch, set up your stuff and then go dive surface interval, a diver would be group C when they started with 7 minutes of RNT at 90' (where a 75' dive at 3000 ft will put you on the table) with an adjusted NDL of 23 minutes.
So in this example the diver would be at the NDL on the dive but not overly at risk of getting bent. The US Navy tables are not exactly considered conservative anymore but fudge factors like diving something other than a square profile, slower ascent rates, safety stops etc, increase the saftey factor substantially.
Check with one of the local dive shops in the area where you dove an see about getting into a high altitude specialty course, or if one is not available, find some experienced local divers familar with high altitude diving procedures and learn from them.
