Did you save your permissions in the options page?
Also what version did you upgrade from? In 1.0.6 there was a change in how categories were saved.
I was actually able to replicate the problem. For some reason term_order was removed from the terms table. so the queries are failing. For some reason this column survived in my development environment. In any case I will work on a fix.
1.1.1 is out. Apparently the column I am using for sorting the Media Categories is now not in the fresh install of wordpress. I have been updating my development environment which did not delete the column. so for a temporary fix I am checking for the column and then re-adding it if its not there. If I get some more time I will look into a better approach.