Couldn't your query just be written as:
SELECT u1.name as UserName from Message m1, User u1
WHERE u1.uid = m1.UserFromID GROUP BY u1.name HAVING count(m1.UserFromId)>3
That should also help with the known speed issues with subqueries in MySQL