I put some backgrounds up here on the site you can download and use, but what if you want a full theme change? Themes exist for free all over the internet.
You download the tsk file and it MUST be installed in your \Windows\ directory. Once there go to Menu->Preferences->Today Settings and you’ll see a list of installed themes you can use.
You will find some excellent and unique themes here ( ppc geeks Themes ). Take some time to wander through the threads.
Tons of themes are here as well.
Several of the online theme sites will let you create and download themes yourself as well.