cannot add categories

This is so frustrating but it looks like a lot of people are having the same problem: I’m using WP 2.5 and cannot add new categories. Sometimes it works and sometimes it doesn’t (usually the latter). How do I troubleshoot where the problem is coming from? What am I looking for? My .htaccess is writable and I uploaded a clean version and re-saved Permalinks just to be sure.

I’m stumped. And my site looks silly w/o categories!
Karri