JB,
It sounds like the theme service is either not starting correctly or could
be disabled.
If you go into Administrative Tools > Services, on the list you will see
Themes as a service. Verify that it is running. If it is not, attempt to
manually start the service by right-clicking it and clicking Start. If the
service starts, try to change your theme again and see if it works. If the
service refuses to start, right-click it, go to Properties, set the startup
to Automatic, OK your way out and reboot the PC. After it comes back up,
verify the service is running.
Regards,