GROUP BY is for use with aggregate methods. Without something like
MAX(contacts_history.dateAdded) it doesn't make any sense to use
I think what you want is along the lines:
SELECT contacts_history.userId, contacts_history.contactId, MAX(contacts_history.dateAdded) AS last_date, contacts.firstName FROM contacts_history INNER JOIN contacts ON contacts_history.contactId = contacts.contactId AND contacts_history.userId = contacts.userId GROUP BY contacts_history.userId, contacts.contactId contacts.firstName ORDER BY last_date DESC LIMIT 0, 10
This should give you (I haven't tested it) one line for each user and contact, sorted by the date the contact was added.