Well, this was an annoying one, and it’s hard to find the one thread that actually addresses it amongst the ones conflating it with an off-by-one error code (subtract one from 0x8004FF91. not going to actually say it here to avoid poisoning Google).
TL;DR if you can’t install Microsoft Security Essentials – even on a brand new install of Win7 64 bit – it’s probably due to Windows Update KB3004394. Uninstall that update, and MSE will install just fine.
UPDATE: KB3004394 has been acknowledged as bad by MS. And the problems are actually a lot more far-reaching than just MSE installs; the KB botched an implementation of root certificate checking that causes all code signing checks to fail. Affected systems (Win7 SP1 and Win2008 R2 SP1 at least) will not be able to install signed device drivers, will not be able to install MSE, will get unexpected UAC prompts in weird places (due to signed code suddenly appearing unsigned and therefore untrusted)… oh, yeah, and Windows Update will fail, meaning that they’ll have to be manually fixed by either uninstalling the bad KB (at which point Windows Update will work again) or by manually downloading and installing KB3024777. Repeat manually – you can’t get it from Windows Update until Windows Update actually works, so…
Get it all in one sock, Microsoft.