Cześć.

Sortuje rekordy po nazwie, lecz rekordy z polskimi znakami są na samej górze, jakieś rozwiązania? (wszędzie utf-8)

dla pola po którym sortujesz musisz ustawic collation utf-polish-ci

W jaki sposób?

1) Poprzez program/aplikację której używasz do obsługi bazy danych
2) Poprzez ręczne wykonanie komendy sql.
http://dev.mysql.com/doc/refman/5.1/en/alter-table.html

Do wyboru do koloru

To samo, nic nie pomaga

A ustawiles?? Bo jakbyś ustawił to by pomogło

ustawiłem, ustawiłem

A na pewno na bazie/tabeli na której operujesz? Bo bardzo czesto ludzie zmieniają lokalnie a działają na serwerze lub na odwrót

To jest ta baza Jestem pewny, że ustawiłem prawidłowo. Naniosłem to na całą tabelę oraz kolumnę widoczną na screenie
tak pobieram:

[PHP] pobierz, plaintext 
$result = mysql_query("SELECT * FROM wojewodztwa ORDER BY nazwa ASC");
[PHP] pobierz, plaintext