Same problem (amongst others) after ICS "upgrade". (My quotes)
Although *some* apps will change the orientation when they start, when I quit them the autorotation will not work.
I have done the pinhole reset, also the factory reset but with no change.
Acer are sending me a voucher to return the A500 for "repair" although exactly what can be done about a firmware bug I don't know.
Although many seem to have gone to ICS without problems, and given that once there you can't go "back", I would think hard and long before "upgrading" if I had to do it again.