YES! I can't believe I didn't try this earlier. This problem has been bugging me for months! Anyway, if anyone is having trouble with their smart playlist order since updating iTunes or to iOS 5, simply right click the playlist in iTunes, DUPLICATE, delete the old one, and make sure the new one is checked to sync. Voila, magically fixed!
Kudos to billynumo and captainjman.
Creating duplicate and deleting old playlist did not work for me. iPhone still shows playlist in reverse order.
I'd be curious though, if you add a new song to the playlist, such as a new one that shows at the top of the list, does it still sort correctly when resynced? I've seen other solutions that worked for me until the playlist was updated and then things were all whack again.