My old Samsung Galaxy S2 with ICS auto rotation fail, i've try to follow some of the suggestion by doing both Calibration - Settings -> Display -> Horizontal Calibration, Settings -> Display -> Gyroscope Calibration. Sorry to say, it's fail and nothing happen.
My solution is pretty simple and it work for me. What i do is i shut down the mobile phone, remove the battery and simcard. After that put them back and start the mobile phone. It's like magic and it's working well now.