Everything installs properly and backups run fine. The problem though is that mail coming into your Exchange server might not be delivered to the end users. We spent over 5 hours with Microsoft and was not able to figure any fixes, they would just get stuck in the Category�s.
Finally we realized that the only major change in the past two weeks was installing the new Backup Exec 11d on the Exchange server. So last night, I uninstalled the backup program and rebooted. Now the server is back working the way it should be.