The process should be as follows:
Run the Cisco UPgradeAssist for CCM 3.x upgrade to v4.x
This will ensure your server meets basic requirements.
Carry out CCM 3.x upgrade to v4.1
Confirm Upgrade successful and Event Viewer for errors, start services from CCM.
Now Upgrade your BARS to the same version you will install on the rebuilt CCM say v4.09
Carry out a BARS Backup.
Now the fun part - Flatten the server by installing the h/w detection disk for CCM v4.1
Install as instructed , and load the BARS v4.09
Now carry out a BARS Restore
You should now have a valid build.