RUgaleFF

SELECT 
  `pm`.*,
  `recipient`.* 
FROM
  `private_message` `pm` 
  LEFT OUTER JOIN `user` `recipient` 
    ON (
      `pm`.`recipient_id` = `recipient`.`id`
    ) 
WHERE `sender_id` = 5 
GROUP BY `recipient_id` 
ORDER BY `pm`.`create` ASC;

Вот SQL решение для моей схемы. Подогнать под Yii проблем составить не должно.
В модели юзеров:

public function relations()
{
return array(
'lastMessage' => array(self::HAS_ONE, 'PrivateMessage', 'recipient_id', 'order' => 'lastMessage.time DESC'),
'messages' => array(self::HAS_MANY, 'PrivateMessage', 'recipient_id', 'order' => 'lastMessage.time DESC'),
}

Выбирать как:

$criteria->with = array('messages' => array('with' => 'recipient'), 'lastMessage');
$criteria->group = 'recipient.id';

Что-то вроде того