Informationweek documents a new issue that appeared under iPhone 1.1.3 which resulted in SMS messages being displayed in the wrong order for some users.
Apple has posted a support document which offers a possible solution.
This can occur if the iPhone is not displaying the same date and time setting as the carrier network time.
Make sure iPhone is setup to receive the network time. Choose General > Date & Time and turn Set Automatically to ON. (Note that in some locations, network time may not be available and in some cases, you may not see this option)./q>