Oh! I'm an idiot!
What you just posted didn't make a whole lot of sense at first. All DISTINCT does is ensure that only one row of a particular value is returned. There is really no sorting involved.
The problem you are getting is that you can't order by a field not having the distinct value attached to it since the server doesn't know which of the non-distinct values to order on. I'll show an example to try and explain it further:
Say you have these values in your table
Now your distinct should return the following: Rock, Classical, Jazz, Techno
Row Number | ID | Genre
1 1 Rock
2 2 Rock
3 3 Classical
4 4 Classical
5 5 Rock
6 6 Jazz
7 7 Jazz
8 8 Techno
9 9 Techno
You want to sort it by ID, but since there is no distinct on that field, should it pick Row 1,2 or 5 for the ID to sort it off of? If it picks 1 or 2, the order will stay the same as I just listed. If if picks 5, the order will now be: Classical, Rock, Jazz, Techno
Which one is correct? The server has no way to know.
Are you looking to sort it by whichever has MORE records on the table? If so, I think an easier approach would be for you to select the table like this:
NOTE: This may not work on PostGreSQL, but it should....
SELECT Genre, Count(*) as GenreCount
GROUP BY Genre
Order BY GenreCount Desc