Mike,
You know what, after reading through this thread, I support your move. I guess the question is do you have the $$ to buy all live sand, and what will you do with the fish while you are doing the cleaning. The problem that I see, if you do not go with all live sand, or at least a good amount of live sand. You will have a cycle in your tank. IMO. Also what about the water. If you are having water problems, then putting all of the old water back in the tank will just cause the same problem.
It sounds to me like you need to completely start over. New sand, new water, but then what to do with your fish? Maybe you could keep them in like a rubbermaid trash can for about 3 weeks. Think of it like a big QT tank. Then put them in your new aquarium. The problem is that if you put them in all at once you will introduce a big bio load all at once.
Who knows I could just be talking out of my a$$.
Scott