I'm getting a similar problem, but slightly different.
When I edit or rename a category and save it, another term_id's name (could be a tag name or category name) takes its place instead of the just-edited category name.
The problem is the term_id doesn't match the term_taxonomy_id; the term_id seems to be incrementing at a different auto index.
So what I have to do is manually go into PHPMyAdmin and alter the wp_1_term_taxonomy table so the term_id matches the term_taxonomy_id in question.
I have to do this every time I want to make a change to a category.
I've taken a screenshot and annotated what I believe is causing the problem:
http://i29.tinypic.com/2noexf.png
Please take a look and give me an idea of how I might be able to fix the problem.
Thanks in advance!