but I would rather leave that and some of the other things you have said as a last resort
There is no magic bullet in these situations. This is just the start of basic troubleshooting and is a process of elimination deliberately designed to locate the root cause as quickly as possible by first removing the most obvious and common culprits via a series of (often) temporary steps.
Do you want to locate and, hopefully, fix the problem on your site? If "yes", then please help us to help you and carry out the changes that we suggest.
Your theme & plugin settings are saved in your database and should be retained for future use. And there should be absolutely no issues with WP 3.6.1. It was purely a bug fix and security upgrade. So this is something specific to your site.