По-моему в том примере все в порядке с сортировкой. Ключевое свойство стора remoteSort: true, т.е. все заботы по сортировке перекладываются на бек-енд. Надо только отловить параметры, которые передает пагинатор:
// параметры для пагинатора
$defaults = array(
'start' => 0, // с какой строки начинать
'limit' => 20, // сколько строк на странице
'sort' => null, // поле, по которому сортировать
'dir' => 'ASC' // направление сортировки
);
$params = array();
foreach ($defaults as $key=>$value) {
$params[$key] = $this->getRequest()->getParam($key, $value);
}
Затем добавить их к своему sql-запросу.