Yep, we got it working this past weekend.
1. Backup Exec 9.1 does not work with the autoloader we have.
2. Backup Exec 10d does not work with the autoloader we have from factory.
IF you apply the patches for 10d to 10.1.5629 Service Pack 1 (I recommend all the way) it does work correctly. The media is recognized as HIC on the tape drive but the autoloader works without any problems now running 10d.
BTW, we did not format the server first. Uninstalled 9.1, rebooted, deleted any left-over files for 9.1, delete all registry settings for 9.1, reboot, install 10d, reboot, patch, reboot, patch, reboot, patch, reboot, ect.... after finish patching initialize, inventory, and backup:P
Problem Solved.