Exactly the same problem with my Windows 7 Pro 64 bit installation. KB3035131 installed OK - not sure why that might be significant. Machine is Intel Core i5 with Windows installed on SSD and My Documents, etc on HDD - Similar setup to ohir with GRUB bootloader. Installation error message was 80004005 similar to Shodan2k.
No such problem on another Windows 7 Home Edition PC or my Windows 8.1 64 bit laptop - all the latest updates installed OK.
No choice but to disable automatic updates on my primary desktop until a fix is available. I need to avoid the pain of a complete reinstall. I wonder how long it will take Microsoft to resolve??