The final resolution of this problem came in two parts.
The code that composes the terms table is in file wp-admin/includes/class-wp-terms-list-table.php, function display_rows_or_placeholder. For hierarchical taxonomies like attachment_category, this function calls function _get_term_hierarchy in file /wp-includes/taxonomy.php to find all the parent/children relationships in the taxonomy. For efficiency, this function stores the relationships in an option field,
attachment_category_children. If the option is present, the function returns its contents without re-computing the relationships.
I believe that the option field has been corrupted for some reason, and no longer reflects the current relationships in the taxonomy. When this happens, there are two ways to fix the problem.
1. You can use phpMyAdmin to find and delete the option value; it will be re-created the next time you display the terms table.
2. You can also force re-calculation by adding a new Att. Category term as a child of any other parent. As soon as I did that, the problem was fixed and everything was displayed correctly. You can then delete the new category and the fix will stick.
In this case, neither of the two fixes resolved the problem. Further investigation revealed that the site was also running the Role Scoper plugin, which makes its own copy of the relationships in an option with a slightly different name (
attachment_category_children_rs). This option also had a corrupted value.
Although I did not hear the final outcome, I think that deleting the
attachment_category_children_rs option would have solved the problem. If not, re-configuring or disabling Role Scoper would be the next step.