smooth4lyfe: thanks for the reminder. i did double check and indeed, Smart Rotate is off. i actually turned Smart Rotate off after i discovered some lag on the S4 shortly after i received it.
I'm on T-Mobile and my screen is rotating at the appropriate times. I applied the update this morning. Is it only in certain apps or it won't rotate at all?
I also had this problem and found that recalibrating the phone's internal gyroscope resolved the issue immediately. Go into Settings and select My Device -> Motions and gestures -> Gyroscope calibration. Follow the simple directions and your issue will hopefully be fixed.