Хорошо, я нашел одно решение моей проблемы:
Если я вхожу в систему как пользователь-администратор и вместо того, чтобы просто запустить мой установщик, дважды щелкнув файл msi или setup.exe, если я щелкну правой кнопкой мыши и выберу «Запуск от имени администратора», моя программа будет успешно установлена.
Похоже, это связано с тем, что на компьютере было включено UAC. Я попробовал это на компьютере с Vista, с отключенным UAC, и программа установки работала нормально, когда работала как пользователь с правами администратора.
Подобный быстрый и грязный подход к исправлению этого можно найти здесь