I was able to solve the problem by:
1. Turning off background sync: Settings -> Accounts
2. Deleting the data: Settings -> Applications -> Manage Applications -> All -> Contacts Storage and "Clear data"
3. Going into Contacts, pressing menu, "Display options", "Sort list by" and selecting "First name"
4. Going back into System Settings, Accounts and re-enabling background sync.
DavidG: Step 3 is how you can sort by last name