Drupal 6 yelling a "Page not found" after clearing the cache

In the process of exporting a Drupal 6 database, I had to empty some cache tables that got really big. To my surprise, Drupal started to show "Page not found" errors for all the pages it served.

After a bit of research I've discovered it's quite a common problem with Drupal 6. In my case, the solution was simple. All I had to do was to run update.php.