[Android Themes] UpwardSpiral:
Okay, here's the definitive answer. *cracks knuckles getting ready for a long type*

First a little back story about how android/java works. Whenever you see any image on the phone (e.g. you your home screen comes up, you open an app, etc. etc.), In the java code, the image is "inflated". What this means is that the view you are currently in is told by the code the name of what should be there and where to find it. It follows the directions, finds the picture and voila! you see the icon or whatever it is.

To theme something, you have two options. The first option is to change the actual image. This is the metamorph/ update zip / everything else method that we've had so far. The actual image is replaced. As a side note, theming related boot loops are usually caused by android trying to inflate an image that isn't there anymore. Whoops.

Then theme chooser came along. The way it works is by giving the phone different directions to the image. the image is still there, but now the phone is looking somewhere else for it (in my app). This way, theming something that's not in your particular phone isn't a problem. It never even looks for it in the first place. This is what makes theme chooser so flexible over different phones. Pretty neat!

So on to the original question. Why reboot? When an app opens for the first time after reboot, that's when it looks up the directions. As long as it is still in your memory, it doesn't look up the directions again. that means no pretty themed colors. Theme manager (the backend of theme chooser) has a solution for this built in. When it applies the theme, it closes everything and re-opens them. The problem is it doesn't work 100% with things that are locked in your memory, like your default launcher and your status bar. Restarting your home launcher is no biggie, and they're working on the status bar. Unfortunately, the fix for the status bar broke something else. Instead of not properly stopping the status bar, now it doesn't properly restart the notification power widget. The app Don't Panic recommended helps a lot with this.

So what does this all mean? you don't need to reboot, you just need to make sure everything is restarted. If you have an idea of what's going on with your phone and use the notification restart program you should be in good shape. I also use the long-press back button to force close an app if it needs to restart (it's in the settings somewhere). The reason I tell people to reboot is because, even on CM7, there is a WIDE range of technical ability. Lot's of people just aren't tech savvy enough to follow the long answer (you should see some of the emails I get from the android market). It's much easier to just tell people to reboot and things work out for them.

So there you have it: the definitive answer.

Appendix A: A word on lockscreen/volume theming. Here is my theory on why these don't theme: I think that, during the boot sequence, these start up BEFORE theme manager does. Without theme manager, there aren't the redirections for where to find the images, so it pulls the image from the normal location. They never stop/restart, so they never theme. Again, just a theory.