This has been discussed a few times with no definite answers, but it seems that auto-rotate gets messed up by certain apps (usually games that run in landscape). One of the more common games seems to be the Asphalt 5 demo that came preinstalled, as well as some other racing games. Try systematically uninstalling games (and don't run Asphalt 5), starting with the racing games, one per day (or all at once then reinstall one per day) and see if that doesn't fix the problem.