It appears that the Sort By Name on the category pages left joins to the LocalizedProperty table which is NULL by default (I only run English so not sure what happens when you start to use multiple languages).
Since the Order By on the category pages uses the product's localized name (and that value is null) both the Sort By Name options (ASC, Desc) don't work.
You can see this on your Demo site. Select any category and change the sort to "Name Z to A"
If there's something I need to do on the setup side to ignore Localization or to automatically populate the LocalizedProperty table LMK.