On BES 5.0.4, it is a bit tricky to add an administrative user. Normal Blackberry users are added under User > Create user, but admin users have to be added from a different menu.

First, login with BESAdmin. Then, you have to go to

Administrator user > Create an administrator user

Then, fill in the fields, which are not self-explanatory:

Display name: Use the display name from Active Directory
User name: Use the AD login name
Domain: Use the AD domain name
Administrator password: Use the password from BESAdmin, not from the user you are creating