Base table missing on Database Restore
Solved by Clive. I had memcached running. It had stored chunks of the code from my original site and tried to run them on the new version. Clearing or restarting memcached solved the problem.

Edit:

An overly simplified explanation of memcached for anyone who's unsure what I'm talking about.

Memcached caches chunks of code. It's best illustrated by a contrast. Varnish caches a static picture of a page and sends that to people when it's requested. It will bypass PHP processing completely.

Memcached won't stop the processing for the page happening each time, but it will remember chunks of the processing and deliver the result straight from the cache.

When I wiped my server and reverted to a backup I forgot to restart memcached. This means that memcached had still remembered chunks of my PHP code. This code didn't fit in with the older revert of my website so I got a horrible error. Restarting memcached or flushing the memcached cache will solve this.