We are running Bllackberry enterprise server for exchange on Windows Small Business Server 2003. What I want to do is add a new user to the BES, but create the user from an External Contact in my exchange server.

When I do this, the user I'm adding always says initializing and when I try to add a device it says the user is not yet known to the Blackberry server.

You can't add a contact to BES.
To add a user to BES, the user must be an actual AD user, with an Exchange mailbox.