I have been having this issue with two websites on wordpress 2.7. The problem happens randomly, usually when someone is using one function or another in the admin side.
The solution is often times random as well. Restarting the database sometimes fixes it (is not fixing my current issue). Sometimes it is just fixed on it’s own with no real explanation.
I have many websites that run on WP 2.7 and I will compare the taxonomy and term tables of a healthy wordpress site against the broken one and cannot find a difference.
I wonder if the WP dev team is aware of this really frustrating issue.