This issue occurs when the VMware Tools installation task is not finished. The guest operating system may already have the Tools successfully installed and running, but the ESX task for installing the tools has not finished.
In vSphere 5.0 and earlier, device backings (what the device is connected to) were not exported. OVF files generated on ESX 5.0 and earlier do not contain the device backing information and therefore do not encounter this issue when importing on ESX 5.1/5.5.
In vSphere 5.1/5.5, virtual machines device backing information is exported. When the Tools install task has not finished it leaves the virtual machine's CD-ROM device connected to a datastore ISO image that cannot be accessed upon re-deployment of the OVF to a new virtual machine, which causes the error.