I think this situation cries out for an InDesign script. I'm not a scripter, but hopefully the scripters can let us know if this is possible.
Thanks for the tip, I did my search in scripting and found an answer: http://forums.adobe.com/message/3407384#3407384
I'm going to try it out now. Thanks so much for your fast responses!
UPDATE: Tried the code above, worked perfectly. I didn't want to mark my own answer as correct (seems like a mean thing to do), so I marked Jongware's correct since it was essentially the same. Thanks again for your help!
HOw did you find/change all tables? I'm trying to select all tables in the document and change their style. I dont' see the option in the find and change dialogue box. How'd you do that?
Jongware's answer is a one-line script, not a find/change query. You need to copy it, save it as a plain text file with the name of your choice ending in .jsx, and put it in your scripts panel folder. You can then access and run it fromthe scripts panel. See How to install scripts in InDesign | InDesignSecrets