Ok - this is weird. I get access denied when I go to /admin ... this is troublesome not only because I can still access admin pages (like admin/people or admin/structure) but also because I have the first user and thus should be able to do anything. Because access is denied to the root of the menu (admin), it won't show the admin menu at all.
I tried uninstalling and reinstalling the admin module (this provides the admin menu) twice, but no change. I also flushed and rebuilt the admin menu - three times. Also did a full flush with devel multiple times. Then I rebuilt all of the site permissions - still no go. Finally, I installed an alternate admin menu which showed the same problem.
I have the same contrib and custom code running on the dev site (different database, but same server), so I am fairly sure that the problem must lie in the DB somewhere... and I fear its the registry or some other dark corner. Any ideas on where to look next?