Yes, I was able to reproduce this. No idea on a solution, though.
I can reproduce the symptoms.
the better way is to create Kali template or standalone VM. Here is the guide:
https://www.qubes-os.org/doc/pentesting/kali/
the advantage it integrates better into Qubes. The disadvantage you will not be able to use the normal menu.
try the following:
1) select the VM you want to upgrade in Qubes OS manager
2) do a right click and select VM settings
3) switch to the Firewall rules tab
4) enable allow full access for x minutes
try to upgrade again.
I could swear I did try that, but I'll do it again when I get home later on and let you know how it goes.
It is very strange, cause VMs (including templates) update without any issue when doing it through the GUI (Right click -> Update VM)