エイリアスを使用したORDERBYのPostgresCASE

サブクエリとしてラップしてみてください：

SELECT * 
FROM 
(
    SELECT users.id, 
        GREATEST(
             COALESCE(MAX(messages.created_at), '2012-07-25 16:05:41.870117'),
             COALESCE(MAX(phone_calls.created_at), '2012-07-25 16:05:41.870117')
        ) AS latest_interaction
        FROM users LEFT JOIN messages ON users.id = messages.user_id
        LEFT JOIN phone_calls ON users.id = phone_calls.user_id
        GROUP BY users.id
) Sub
ORDER BY
  CASE WHEN(
    latest_interaction > '2012-09-05 16:05:41.870117')
  THEN 0
  WHEN(latest_interaction > '2012-09-04 16:05:41.870117')
  THEN 2
  WHEN(latest_interaction > '2012-09-04 16:05:41.870117')
  THEN 3
  ELSE 4
  END
LIMIT 5;