По-моему в том примере все в порядке с сортировкой. Ключевое свойство стора 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-запросу.