Veeam Availability for Nutanix backup fails after upgrade to AOS 5.8.0.1 or later

Veeam Availability for Nutanix backup job fails with:

Backup VM [ID: 4a89ffc5-68b3-4be0-b117-0591dcec184e' Name: 'MYVM’] failed. Error: Backup was unsuccessful. Preparing VM for backup failed, 1."

Prism Element dashboard shows the following failed tasks:

The following conditions are met:

1. Nutanix AOS is upgraded up to 5.8.0.1 within STS (Short Term Support) release branch;
2. Affinity rules are configured for the affected machines:

This is a known Nutanix issue and is tracked by Nutanix as an internal bug ENG-163615 which was discovered after the release of Nutanix AOS 5.6.1.
 

Upgrade to AOS 5.9.1 where ENG-163615 was resolved.  If an upgrade is not an option, you may disable the host affinity rules for the affected VMs as a workaround.
 
LTS (Long Term Support) release branch is not affected by this issue at the moment.