I had the same install and uninstall issue (0x80004005). I resolved the issue by manually deleting the Zune firewall rules in the Windows Firewall and then performing uninstall/install. I am running Windows 7 (x64). I used the Windows Firewall with Advanced
Security tool in Adminstrative Tools to delete all inbound and outbound firewall rules for Zune components. Hope this helps.