I have Samsung Galaxy nexus running official Android version 4.2.1. Problem is that the auto rotate toggle on the power control widget is not working properly. The toggle will change state, but the auto rotate feature state is not changed. I have to go to Settings -> Display -> Auto-rotate screen checkbox to change the auto rotate feature. The toggle button on the power control widget is unable to change this checkbox status.
I was wrong about the setting, it wasn't the auto rotate button. Power control widget doesn't have auto rotate, just Wifi - BT - GPS - Sync - Brightness.
What you consider to be the auto-rotate toggle, is the button to switch the sync! It will switch whether your device will sync in background or not.
I use SwitchPro Widget app instead of the power controls. So many more options and customizable. Not free but only 99c. It has a Auto Rotate Toggle among many more switches.
I too was thinking the sync button on the Power Control widget was the auto-rotate buttong. However I've found that by touching the top status bar and dragging it down gives me an auto-rotate button without having to go into Settings, etc... This is available while inside most apps so you don't have to exit to go to the settings panel.