Here's the issue, modelled on my Lumia 930:
Hard ('factory') resetting a phone is a clichéd fix, of course. It's what support desks often ask you to do and, in this case, it turns out to be the only fix that's permanent. Clearly some file or setting under the hood is hanging around from pre-Denim days and causing issues. But, as already intimated, the very act of doing all this will give you a cleaner, fresher OS that will probably be faster in day to day use. And - hopefully - all your 'stuff' will be restored. Here's what to do and how I got on.
1. Do a backup
This isn't a given. Although most people have their core PIM data synced through a server on Google or Outlook/Live.com, all your applications, settings, SMS, and more, may not be automatically backed up and you may need to turn this feature on. Go to 'apps+settings'/'backup' and check this setting.
Even if on, best to tap on 'back up now', so that you're bang up to date. The backup process may pause, halt or even terminate, but perservere - try again. There's a lot of data being uploaded and success depends on what your phone is doing, its connectivity status on Wi-fi and the status of Microsoft's servers.
2. Factory reset your phone
Gulp. But it'll be OK, as long as you backed up and can remember your app and service passwords (please say you've written any such down somewhere!). 'settings'/'about' use the 'reset your phone' button and wait...
3. Restore!
Make sure you have your main SIM in (it's used as extra ID) the phone. After entry of your Wi-fi router password and essential Microsoft account details, you'll be prompted to restore an existing backup or (if you scrolled to the bottom of the list) start from scratch. Obviously, select the backup you just made and then tap on 'next'.
The core settings, Start screen, PIM data and so on will come back quite quickly, I had to wait only about five or ten minutes. However, note that the reinstallation of all your Store applications takes a lot longer - the restore remembers what you had installed, including settings and data for some, though it will take time for them all to physically download and install - around an hour in my case, though at least you can use the phone in the meantime. Just don't be too impatient!
Result
I have to report complete success - I've no idea what hangs around from Lumia Cyan that causes auto-rotation problems due to interaction with Lumia Camera 5, but there was definitely something. I and others round the web have experienced complete success by resetting in the manner described above. I've been playing with the phone, its camera and landscape applications for two days solid now, and auto-rotation is as quick as it's ever been.
The total time taken, from starting the backup to finishing putting in my last few notification settings and email passwords, was about an hour and a half, but most of that was watching progress bars (backup, reinstallation) crawl across the screen, it was all quite easy.
What did I lose? The only thing of any significance seems to have been the 5MP oversampled versions of photos and any .nar archives of Rich Captures. Of course, all photos were backed up in 16 or 20MP form on OneDrive and it was easy to re-download my favourite 40 or 50 from recent times - but there's no way to now fiddle with Rich Capture customisations. Not a showstopper though - most Rich Capture tweaks were done at the time and the results auto-uploaded, plus if I really wanted 5MP versions again then there are plenty of utilities on the desktop that can downsample the high mega-pixel versions on OneDrive.
Of course, extra data points are welcome here. Have you been plagued with this issue and if so, on what phone? Did you try the procedure above, did it fix the rotation problem, and did you lose anything of note other than what's mentioned above?
PS. In case you were wondering, no, this issue wasn't fixed in 8.1 Update 2 - it's purely and simply an artefact of leftovers from 8.1.