What is your setting under "Configuration" - "All Listing" "Display Product Display - Default Sort Order"?
Mine is set to "1" which results in the products being sorted alphabetically by "Product Name" if all sort orders are the same value. However, if I change the sort order number for the product, it overrides and sorts by the value first and then by product name.
This site is not yet live, but it may help. If you would like pdf files of my configuration settings, I'd be happy to share them.
http://www.uniqueideasnmore.com/shopping