Please correct me if I'm wrong, but my understanding is that this remapping layer was not somethng demanded by the software license. Renaming files and fixing internal references to it would be enough to meet the requirements of the license and to distribute fully-functional software.
The catch, if you can call it that, is that pre-existing programs (documents) that referenced the file names that were no longer there would no longer just work on the modified software. They'd have to be mechanically modified as well.
I won't get into the debate of whether exposing internal implementation details as part of the public API is a good idea, even more so when these details must be modified when the progarm changes. However, nobody prevented the modifiers from implementing a script to make the needed changes, all mechanical, and the fact that it could be done in lower internal layers of the modified software, rather than as user-visible API changes, goes to support, rather than detract, from the fact that the original software was indeed Free, and I only bring this up because someone might make a successful case that, if it wasn't so, then some important freedom was missing.
Having the freedom doesn't mean its enjoyment has to be effort-free. Even the most permissive licenses carry some requirements with them, as light as keeping copyright notices intact and not removing the copy of the license. Copyleft licenses are more demanding, but none of the requirements, by themselves or taken as a whole, prevent you from enjoying any of the freedoms (although the combination of those requirements with others one might have accepted may have that effect, which makes it copyleft).
Some trademark issues have similar effects to those in TeX, but that the requirements are enough of a pain that some people set out to replace all the trademarks and logos ahead of time, to be able to keep that out of their minds in subsequent relevant modifications, is, to me, an indication that the freedom is there, just not so trivially accessible.
I like the metaphor that respecting someone else's freedom is not giving her a ride to the place she wants to go, but rather refraining from placing or keeping unsurmountable roadblocks on her way.
So I stand by my understanding that TeX is Free Software, just like Firefox is Free Software. If Debian read its heuristics in such a way that it reached a different conclusion, and (assuming) for this reason alone it set out to create IceCat, may an indication that the tide is turning, and that the essence is being lost and the heuristics taking over. If that is so, it is very sad. OTOH, it may very well also be that Debian just needed to make the changes and figured sharing it with others was the best way to go. If that is so, it is very good.