My device Auto-rotate suddenly stopped working without any reason. I verified that “Auto-rotate screen” was still turned on in my Acessibility settings. I also tested and recalibrated the sensors with the excellent free Sensor Tester by Soaus without success.

After reading some advice about cleaning the cache I looked into the issue and found a simple solution that worked for me. Using a cache cleaner (Titanium Backup) I simply cleaned the cache of the “System UI” application, rebooted and Auto-rotate worked for me.