The technical steps are indeed trivial, but the user confusion cost is high.
When using the trademark, you can't make changes without Mozilla's permission - i.e. you can't apply security patches. Despite this, distros such as Ubuntu have accepted the trademark restrictions, so they've obviously estimated very highly the user overall cost of removing the trademark.
I don't know the whole Debian story but I think it's that they switched to their branding before the "unbrand" feature was added to the Firefox compile process. You might find the answer on http://en.wikipedia.org/wiki/Mozilla_Corporation_software...