This is a very odd issue. Logged in as admin. All permissions given to admin. But Access Denied page when I try to flush cache or change theme. I can flush the cache with drush. I tried switching theme to garland and back again. I tried creating a new admin user, didn't work. I tried disabling recently enabled boost module, to no avail.
I have no idea why, but I disabled clean-urls and reenabled it and now I can flush cache and switch themes without access denied.
I had installed the Boost module which also involved putting some stuff in the .htaccess and turning on clean urls (although I was using it anyway).
This problem took me about 4 hours to solve and was completely unintuitive.
I experienced this issue and it turned out to be a problem with the admin-menu. Clearing caches worked when triggering from Performance admin workflow.
In my case this problem occurred after installing a custom permissions-related feature which included some permissions for the admin-module. I recreated the feature without these and then reinstalled the admin-menu module and the problem was resolved.
Hope this helps.