[forbesn]

Don't know why this worked. We went to this option in order to change some columns to hidden. (See http://nickgrattan.wordpress.com/2008/12/02/changing-order-hiding-columns-in-new-edit-forms/ if interested in hiding columns)

1. Open the list and select Settings + List Settings
2. Select Advanced settings
3. Click Yes for “Allow management of content types” and then click OK.

Now the sort order works.