Guys, as I stated in an earlier post I am new to installing themes. I am running Bo's deodexed .596 and I installed the Watermark'd theme on it. I would like to try a different theme now. Can I flash over the existing theme? Do I need to flash a fresh .596 first? Can I flash a nandroid of my unthemed .596 then flash the new theme?
You can, but I suggest you apply the deodexer again, and then apply whatever theme you want after that.
Sometimes those backups are finicky. If you have FC issues, apply the deodexer after restoring, and even if you don't have FC issues, I still suggest you apply the deodexer again.