Before removing and re-adding the user, you should always check the connection. Under "Manage Connections", if you click on "Services Status", you should see:
Code:
Mobile Voice
Status: available
Connection: Mobile Network
BlackBerry Internet Service
Connection: Mobile Network
BlackBerry Enterprise Server
Connection: Mobile Network
You should also check on the server, when the last contact time of the user was. Most of the time it is a connection problem and deleting the user does not help to solve that. A cold restart of the device is also something to try.
But now you have run into another problem. Sometimes it can take quite a while until a user is deleted from BES. Before re-adding you should check under "Users Pending Delete" if the user has really vanished. You cannot add a user when he is still in the Pending delete state.