I found the "problem".
It seems that the code of the systemd script that detects virtualization
(systemd-detect-virt) has changed between fedora-23 and fedora-24.
The one in fedora-24 is confused by the fact I use QubesOS insed a KVM
VM and is not able to detect xen on top of the VM (it detects KVM
instead). As a consequence, the service xendriverdomain.service was not
started (ConditionVirtualization not met), causing networking to not
work on the AppVM (as the backend network was not correctly configured
on the NetVM side).
To workaround this "problem" I overwritten the systemd-detect-virt in
fedora-24 by the one in fedora-23.
Everything works fine again :)