Tente envolvê-lo como uma subconsulta:
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;