reinstall SBS with the same computer name.
Restore the exchange Information store. Do not restore the Directory store.
Start MsexchangeSA
Start MsexchangeDS
Run eseutil /p /ispriv
run isinteg -patch
start MSexchangeIS
start MSexchangeMTA
start MSexchangeIMC
goto configuration->servers->servername properties, run the IS/DS consistency checker
check all boxes, click on all inconsistencies,
click ok, accept the Public Folders warning
this should restore your IS and Directory structure.
Hope this helps. Because I have been there and done that, not a pretty sight.
Let me know if you have any more questions.
Besure that the restored exhange is at the correct service pack as your backup.