So I started posting my troubleshooting steps and frustrations on Twitter and a Drupal friend of mine, Mark Jarrell, stepped in to help.
We got it narrowed down to the new themes and he had me look for preprocess code involving vid/tid in the template.php files.
Sure enough, there was some code that Acquia gave me last year in the template.php files. I removed the code and it solved the problem. Thanks Mark!