There seems to be a problem in Backup Exec 2012 in how it detects virtual windows servers (Hyper-V) as being virtual rather than being physical boxes.
When you backup new virtual servers on the host machine, Backup Exec normally adds the newly discovered virtual servers to the selection list as virtual servers with the blue virtual server icon.
However, if you have already installed the Backup Exec Remote Agent for Windows Servers inside of the virtual server prior to backing up the virtual server for the first time, Backup Exec sees the server as a physical box and adds the virtual server to the selection list as a physical server. Backup Exec then says this server has never been backed up and you can not do any granular restores of the virtual server.
The workaround for me was to delete the mis-identified virtual server from the selection list. Uninstall the Backup Exec Agent from inside the virtual server. Then do a backup of the host again. Backup Exec then sees the virtual server as virtual again. Then reinstall the Agent inside of the virtual server again to get full GRT support.
(It may also be possible to just temporarily disable the Backup Exec Remote Agent service rather than uninstalling it so that the backup server can not communicate with the agent. That should have the same effect as it breaks communication with the backup server.)
Backup Exec 2012 needs to be patched so that it can detect new virtual servers as being virtual even when the Backup Exec Remote Agent is already installed inside of the virtual server prior to being backup up for the first time.
Hope this helps anyone else who has this same issue.