Подведем итоги.
Нагуглили следующий гайд:
Пуск -> Выполнить ->
regsvr32 msi.dll
msiexec /unregister
msiexec /regserver
Если проблема не решена, переустановите Windows Installer 4.5 (http://www.microsoft.com/downloads/details.aspx?displaylang=ru&FamilyID=5a58b56f-60b6-4412-95b9-54d056d6f9f4)
Попробовал выполнить действия в cmd — безрезультатно. Windows Installer не переустанавливал так как проблема повторилась у моего друга. ;)
Evernote v4.1 не хочет устанавливать даже на ОС на которой его не было до этого.
Проверяли на Windows 7 x32 / 64 Enterprise.
Вот такие пироги. Склоняюсь к тому, что грабли на стороне дистрибутива Evernote.