Hi, the simple option is to delete the users from BPS and then uninstall the software. Once the software is removed install BPS on the new server and reactivate the users (you will need to wipe the devices first). Or if you want to move the server without affecting the users follow my guide in the link below:
http://www.blackberryforums.com.au/forums/microsoft-exchange/3073-bes-4-0-x-4-1-6-upgrade-plan.html#post10021