First, the query does not make sense:
SELECT IF(p2u.last_viewed<pm.datetime,true,false) AS unread,
pm.id, pm.conversation_uuid,
pm.subject, pm.datetime
FROM pm2user AS p2u, pm
WHERE p2u.conversation_uuid=pm.conversation_uuid
AND p2u.user_id=1
AND p2u.folder_id=1
GROUP BY p2u.conversation_uuid
ORDER BY pm.id DESC
LIMIT 0, 15;
You are GROUPing BY something, but the fields you are selecting are not unique to the group or are not "aggregrates". Which datetime do you want? Which id do you want?
Second, this is a classic difficult query -- Joining two tables, where clauses on one, order by the other, plus limit. It effectively has to gather up lots of stuff before the group by, then sort, finally deliver 15 rows.
What are the indexes?
To assist in analyzing slow SELECTs, please provide
* SHOW CREATE TABLE tbl\G
* SHOW TABLE STATUS LIKE 'tbl'\G
* EXPLAIN SELECT ...\G
and surround them with [ code ] and [ / code ]
You need index that _starts_ with user_id and p2u.folder_id because those are the fields for which you have WHERE clause filtering.