New menu items don't appear after upgrade D6->D7

Folks,

We have a really strange problem with a medium size site that has been upgraded from a D6 to a D7 (7.10).
The upgrade was fairly easy (as easy as such processes can be), and the site is running as expected except for one pretty major thing:

No new menu items can be added.

And with adding menu items I don't mean creating menu items in user menus manually (that works), but having D7 itself add menu paths as a response to installing modules, creating content types and much more.

It simply doesn't happen!

If we add a new content type called test_type, we should get a new menu item under node/add, but we don't. The path node/add/test_type leads nowhere and checking the menu_links and menu_router table tells us that they don't exist.

Same thing if we activate a module, say Dashboard. Normally we'd get a new link to click in the admin menu and the path admin/dashboard should lead to the Dashboard, but neither works.

If we add a menu item to hook_menu in one of our own modules, say /testing_menus as a callback, which returns some sort of banal page content, I get a page not found when trying to reach /testing_menus.

We have tried many things: Flushing caches, running update, uninstalling and reinstalling modules, fiddling permissions. Nothing changes this behavior.

I have no idea why and what can be happening, but it's pretty counterproductive, and essentially halts all expansion on the site.

Has anybody seen anything like this or does anybody have any ideas where too look for the cause of the problem?

Martin