I would try and reboot the phone. Hold the sleep/wake button and the home button together until you see the Apple logo and then release. See what that does. I'm going to try and change my sort and display order on my phone after I finish this and let you know. I'm using a 3G with 4.0.1
EDIT: I just changed my sort order from last, first to first, last and the display order I've always had is first, last. When I did that and went into the contact app and then into the phone app and touched contacts, they are sorted and displayed by first name. I normally have it sorted by last name and displayed by first name and is looks the same in both locations. See if that reboot helps. I didn't have to reboot my phone at all, it just changed.