A Wii should never have any sort of alternate theme, template, etc. as such things can only be changed via modding. Uninstalling works in the same fashion, unfortunately: you'd need to look into modding yourself to remove it (which is very dangerous for the Wii if you don't know what you're doing).
As for Ocarina of Time, I'm sorry to say it will not be restore-able for two reasons: first and foremost, your Wii was modded and therefore Ninty won't have anything to do with it. Secondly, even if that wasn't an issue, you'd need proof of purchase to re-download OoT... which is kept in your Wii Shop Channel's account. I believe that's all lost upon reformatting.
My apologies for bearing nothing but bad news.