From what I can tell, rpm package generation changed slightly (very recently) which might be incompatible with the version of rpm used in a fresh 4.0.4 install. Added some notes to the GitHub issue.
Demi (who is on the official Qubes team) pretty much confirmed we can work around it by upgrading rpm first, then doing a normal update, but let’s wait for an official course of action to follow.