Had this problem as well. Tried everything: reset, reset all settings, tapping the device etc. to no avail.
Tried installing a level app to test, and the accelerometer was completely dead. My conclusion: broken accelerometer.
As this was too expensive to have fixed, I looked to a way to switch the orientation in software, so here's how to do this:
Go into Settings --> Accessibility --> Triple click --> and enable AssistiveTouch
Now when you triple click a little dot will appear on screen. Tap that, then tap Device, the Rotate Screen and you can change orientation even though the accelerometer is dead.
Now to the most surprising part: after doing this, my accelerometer has started working again, hurrah. I don't know if this will be the case for everyone ( obviously if your accelerometer is really dead, it will not work for you), but even if it does not work, you will be able to manually change orientation.