Is the association in question perchance a self-reference? One that runs from the top-level entity to the same entity? Because sorting over references has always been a questionable proposition in Mendix. If sorting is absolutely necessary you should probably try to avoid self-references altogether.
Maartje,
I created a little test for this and saw that the sorting does work, however the empty values will always be sorted a the first item. I created 2 entities, one for the normal attributes and one for the association. Created associated records with attribute values a and b. When adding the records for the entity containing the association, I created 3 record. One with association to record a, one with b and one without an association. When sorting in the datagrid I saw a and b switching order (first a then b, then b before a), but the record with the null value for the association will remain the first record. This seems to be intended behavior as the null values need to be sorted differently, see for example a java question on sorting nulls here