Before trying these steps, make sure that you have restarted your iPhone. Also note that some apps do not allow for the screen to sideways and therefore will never change to landscape orientation. But if nothing (pictures, web pages, etc.) will never rotate, then try these steps:
1) Double-tap the home button (black button at the bottom center of your iPhone) until a menu of apps appears as a bottom row on your screen.
2) Swipe the row to the left. You will see iPod controls plus at the left-most side an icon with a clockwise-pointing arrow.
3) If this arrow circle has a lock in the center of it, then it means your landscape mode is locked. Tap it to unlock it.