Для начала лучше залезть в Windows\Start Menu\
или как оно там называется, щас уже не вспомню, в папке должны лежать все категории и ярлыки из меню пуск, вероятно их просто нет или они битые.
Как вариант взять Resco Explorer и им создать ярлыки по новой. (или же попросить копию этой папки у другого владельца такого же девайса).
Если не поможет тогда уж хардресет.
До кучи не плохо бы перед х.р. Проверить комун на вирусы, что бы знать есть ли они и какие именно (дабы не повторить инциндент).
#2 можно и без меню, просто тапнуть на нужный ехешник, эффект тот же