Hi Folks,
in my setup the cause was indeed that I had to move the admin mailbox for the Blackberry Admin user. Though its MAPI-Profile got updated correctly, one has to execute handheldcleanup.exe -m from the utility directory of the BES Installation.
I found the solution here, worked well for me.
PDA street forums - BlackBerry Enterprise Server 3.6 Upgrade
Bye,
PHPat