Delete the fired employee from the BES server and do a security wipe on the handset.

Create the new employee and generate an activation password, then go into enterprise activation on the phone and activate the new user with his email address and activation password.