Here's the one I get, word for word:
Installation Failed
Setup must stop because the required package '%1!s!' failed to install.
Error code: 0x81000109
Now, I've tried both the standard download and the full package and get the same error, regardless.
http://download.yousendit.com/BEA77FB21CA74FEE
I am having the same problem as a lot of you. That above is the Zune 1.3 installer, I downloaded it last night just in case I had to go back to 1.3.
Windows Firewall seems to be the 'missing package'
Turning ON the Windows Firewall fixed this for me.