I guess my biggest problem with the whole notion is the fact that I affect record A. In Oracle's tree representation (and I'm assuming PG's, as well), that's the end of it.

Just in case this wasn't clear before. If you're RDBMS supports tree structures natively use them. Using nested sets in this case is obviously a pointless reinvention of the wheel when you already have a native mechanism for querying/updating trees.

However, if your DB doesn't support tree structures well or if you need to consider the possibility of migration to a DB that doesn't support them then nested sets are pretty darn good in my experience.

With nested set trees, I might have to re-number the entire hierarchy's intervals.

Yup. As I mentioned before insertion is O(N). You can make the average case a lot better by sneaky work with the intervals.

However since the vast majority of applications read a lot more than they change the hierarchy the more efficient queries more than make up for the less efficient inserts.

Another thing that concerns me is how this might potentially affect triggers written against that table.

I fail to see how this is any more/less of an issue than any other representation?

Most developers work with tables that aren't nested sets. (I understand that's how RDBMS's think about things, but most developers of my acquaintance aren't as ... flexible.) The data structure, as a whole, looks very fragile to me. There's a lot of bookkeeping involved (unless I'm missing something obvious).

You wrap the bookkeeping in a client side API or stored procedures on the database side - just like you would with any other bits of repetitive SQL.