Backup Exec uses the vStorage APIs to backup VMs residing on ESX hosts. Without this license, these APIs cannot be invoked by Backup Exec's Vmware agent. It could be highly possible that with your ESXi 5.0 hosts, the free license of VMware included the vStorage API option.
Best way to be sure would be check the licensed features of the other ESXi host which hasn't been upgraded yet. And if i recall, the free edition of ESXi 5.0 did come bundled with many APIs and lesser restrictions, however best to check with VMware regarding the licensing differences.