The back up and nuke-it-from-orbit solution (maybe):
1) Back up your database and download your wp-content directory
This is essential. Do not move on to the other steps until this is done and you can confirm that the database backup is good.
2) Drop your old database on the server (that means delete it).
3) Create a new database on the server
4) Install WordPress and confirm that it works
5) Import old database information into the new database. You will likely have to break this into sections as MySQL and PHP, for good security reasons, have timeouts on transactions.
6) Confirm things work correctly after importing old database records.
7) One at a time, upload your themes and confirm that they work.
8) One at a time, upload plugins and confirm that they work.
9) If, at any point, something goes wrong or this issue appears again, identify the last action you took and see if that helps you identify the root issue.
* The above steps are not to be taken likely and it may be best to do a trial run using a local testing environment first. This stuff is dangerous and should only be done if you feel the reward is worth the risks of *destroying* your existing database, re-installing WordPress from scratch, and carefully re-builiding your site.