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