Replying here since I came across this from a google search as the issue happened to me on a brand new 4.1 install. This may not be entirely correct but it did work for me (I did not attempt the rpm install but assume that would be more of a correct solution).
From the releases page previously linked, download the latest ISO.
Now you need to get that ISO into dom0, I was able to use the qvm-run command similar to what was in the guide, make sure to change YOUR_QUBE_NAME to the Qube you downloaded the ISO into:
dom0
qvm-run --pass-io YOUR_QUBE_NAME 'cat /home/user/Downloads/qubes-windows-tools-4.1.67.1.iso' > ~/qubes-windows-tools.iso
Now we replace the existing ISO with the new one:
dom0
mv qubes-windows-tools.iso /usr/lib/qubes/qubes-windows-tools.iso
Try to create a new Windows Qube and it should breeze through now!