cache_clear_all will fail during module enable if the table being cleared does not exist yet. Usually, cache tables always exist at cache_clear time if they are defined in the module's schema method (as they should be). If a module adds a new cache table, then it should provide an update function to create it. However, when doing a major upgrade, the contrib module upgrade procedures at http://drupal.org/node/948216 (referenced from both Drupal 7 and Drupal 8's UPGRADE.txt) instructs the user to enable the module before running updatedb. Enabling the module calls cache_clear_all, which will fail. The new table was not created by the install function, because the module was installed earlier, before the table existed in the schema, and it was not created by the update function because updatedb was not run yet. When upgrading from Drupal 6 to Drupal 7, the token module is one example of a contrib module that fails in this way.
The workaround is to ignore the error and run updatedb. If this is the sanctioned solution, perhaps the documentation should be changed to warn upgraders about this eventuality. Drush Site Upgrade could be modified to automatically try to run updatedb if the module enable fails, but this solution seems slightly inferior.
The attached patch adds a check in cache_clear_all to see if the table exists yet before clearing it. This allows the upgrade of modules that add cache tables to their schema to proceed cleanly. D8 has a different cache implementation, but it would not be hard to do the same thing there. I'd like to hear what the general consensus on the desired behavior should be here before doing that, though.
Edit: The patch here is not good, and should not be used. See #1 below.