Depending on the version of SBS you need to Service pack and apply all updates before you install Exchange. I have to assume that this is the only SBS server and that if you have other Domain controllers they are replicating correctly. Check trivial things like time on the server, run dcdiag and netdiag.
Also when you say “clean re-install” you mean, you wipe the drives with the OS and re-install the SBS from scratch, other wise do so. You do not have to wipe the DATA partition or array. You may want to rename all exchange DB files install and rename back pointing the store to those files.
Hope soe of this helps.