This technote:

http://seer.entsupport.symantec.com/docs/308416.htm

suggests the brute strenth and ignorance approach of keep trying the conversion until it does succeed.

Do you have a 32 bit XP workstation or 32 bit Win2k3 that you could attempt the conversion with?  The conversion does not necessarily have to be done on the computer that created the image.

You can also try perfoming a restore within a virtual machine by booting the virtual machine to the recovery environment.

Restoring Server 2008 can be tricky and may require some advanced options. When selecting the Restore Anyware option, hold the left ctrl button and make sure that all three options that appear are unchecked.

I tried both of your suggestions, but neither of them seems to work. 

I ran some tests: 

1) 
As stated previously, when I try to do a conversion of a Windows Server 2008 R2 image on a Windows Server 2008 R2 host server, the process always fails with the error code:
-Cannot convert image file.
--Error EBAB03EE: Operating System API [RegistryOperations::UnLoadHive] RegUnLoadKeyW( PQ_TEMP ) failed.
---Error EBAB03F1: The system cannot find the file specified.

2)
I tried to do the conversion of a Windows Server 2008 R2 image on a Windows Server 2008 R1 host server.
This fails with the error code:

-Cannot convert image file.
--Error EBAB03EE: Operating System API [RegistryOperations::ElevateSubKeyAccessRights] RegOpenKeyExW( TARGET_HIVE_SYSTEM\Setup\SetupCL, READ_CONTROL|WRITE_DAC ) failed.
---Error EBAB03F1: Access is denied.
 
I kept retrying this, but I always get the same error. 

3)
When i try to restore a Windows Server 2008 R2 BackupExec backup to a new virtual machine, the process completes successful. 
When I try to start the new virtual machine, I only get a blinking cursor. 
I also tried this using "restore anywhere", but again, I only get a blinking cursor. 

4) 
When I do a conversion of a Windows Server 2008 R1 image on a Windows Server 2008 R1 host server, the conversion succeeds. 

Could it be possible that BackupExec is having problems with the image of an R2 version of Windows Server 2008?