Уточню:
-Из "Пуск"-"Все программы" ярлык не работает (IE не запускается)
-Через запуск с ярлыка на "рабочем столе" - тоже. После переустановки с "рабочего стола" запустился и работает, а из меню "Пуск" - нет.
Если это так и Вы хотите, чтобы он запускался и там, и там, то:
Открываете меню "Пуск", наводите на значок IE мышь, правым щелчком открываете меню и выбираете "Удалить" (можно переназначить, то заменить будет проще).
Наводите мышь на Ярлык IE на рабочем столе, нажимаете левую кнопку и, держа ее нажатой , перетаскиваете ярлычок прямо на кнопку "Пуск". Держите пару секунд и меню откроется. Далее "протаскиваете" на нужное Вам место и отпускаете. Всё, ярлык рабочий.