А что если сделать чекбоксы в отдельной колонке (ну, преположим, 16 пискселей) и дать возможность сортировать по ней? причем, один клик - сортировка, воторой - обратная, третий - без сортировки (!). Сортировка по этой колонке будет дополнительной к остальным, т.е. таблица всегда будет сортироваться с двух позиций - относительно галочек, а уже потом относительно нужного поля. Это было бы решением проблемы.
 
Dervish: Если честно, то я уже подумываю совсем отказаться от группировки записей по чекбоксу. Действительно, это не есть хорошо.