I was having the same problem of slow posting/editing, but fast for everything else. The problem for me was the “Google XML Sitemaps” plugin which generates a sitemap for search engines. I could see that the MySQL changes were written quickly, but then my site would be frozen.
The fix was to uncheck the various options to notify search engines like MSN, Yahoo and Ask. I think one of them wasn’t responding quickly, and the plugin was taking a long time to timeout. I left Google checked (since they are where most search traffic comes from) and that is fine. Now it is back to very speedy edits/posts. I haven’t gone back to determine which specific service is the culprit.
And I didn’t convert my categories to tags, and this is on 2.5.1.