After another failure and more research, here's something to try if you get this error: Go to [WoW Directory]\Data\ and delete Patch.mpq (ok, don't delete it but rename it just in case). Then run the repair.exe utility in the wow root folder. It will tell WoW has a critical error and needs to be repaired. Let the repair run (it may take a little while).

Then try running the game again and let it patch.

That's what I'm trying now and will see how that goes.