In Skylanders on the Wii, is it possible to start over, deleting what you have played and upgraded to so far?
There are two parts to the game's progress. There's the story progress, which is stored in the game's save file, and there's character progress. Starting one over would not affect the other.
To sum it up, if you want to completely reset the game to it's initial state, you'll need to reset all characters in the method specified and delete the save.