Tom, the gas is hydrogen sulfide. OrionGirl, what they are metabolizing is not nitrogen in any form but sulfate to sulfide. They only do it when nitrate is exhausted. Other bacteria in the same community are making a living oxydizing sulfide back to sulfate. All happening quite deep, and in a sediment that remains undisturbed, like gregga's.
"Burps" from the gravel, if it's deep and also organically enriched, could also be methane, which isn't very soluble. But isn't the likeliest "burp" gas just carbon dioxide? Or would CO2 always remain in solution?
If gregga's fish died of H2S poisoning, the unmistakable, gag-making odor would have filled the room. Hydrogen sulfide is not merely skanky-smelling. It's as bad as shaking ammonia with bleach. Other nasty sulfurous smells, like onions gone rotten, are thiols a.k.a. mercaptans.
What about the alternative possibility? That normal processes of bioacidification depleted the carbonate buffer and pH had dropped; harmless NH4 had built up, since nitrifiers go dormant at pH in the low sixes; then when most of the water was removed in order to shift this 20-gal. tank and was replaced with fresh, the buffering was instantly renewed, NH4 converted to NH3, and the fish were overcome with ammonia poisoning. What is sometimes called "Old Tank Syndrome."