[Котяра]

Сама служба тем работает, я пробовал ставить и авто, и вручную... »

NADVooDoo, вы в этом уверены? Как смотрели?
После установки патча перезагрузились?
Что у Вас в папке C:\WINDOWS\Resources\Themes? (Это папка с темами.)