Mysql – Slower queries after upgrade from thesql-5.5 to thesql-5.6

There is lots written about how MySql 5.6 is faster than MySql 5.5 (e.g. http://dev.mysql.com/tech-resources/articles/mysql-5.6.html) but we upgraded our Amazon RDS instance (using the new upgrade procedure) and found that the average time spent in the database per page view got worse, from 30ms to 50ms – a significant slow down.

This is a chart (from newrelic) of the Time spent in the database per page view (approx 1000 queries per second):

The slow down seems to be on simple UPDATE statements. I wouldn't expect them to be a problem because the PK is used. This example shows a statement that took 6 seconds to execute but the explain plan is optimal (rows in table: 700k):

mysql> EXPLAIN UPDATE users SET type='dual', updated_at=NOW() where user_id=1234;
+----+-------------+---------+-------+---------------+---------+---------+-------+------+-------------+
| id | select_type | table   | type  | possible_keys | key     | key_len | ref   | rows | Extra       |
+----+-------------+---------+-------+---------------+---------+---------+-------+------+-------------+
|  1 | SIMPLE      | users   | range | PRIMARY       | PRIMARY | 4       | const |    1 | Using where |
+----+-------------+---------+-------+---------------+---------+---------+-------+------+-------------+

updated_at=NOW() seems to be a common theme in the newly slow statements.

Is there any reasons UPDATEs are slower with MySQL 5.6? Does anyone have any clues about what I could check to debug this slow-down?

Other info: instance size: db.m2.4xlarge , query_cache is off. performance_schema is off. exact versions: was: 5.5.27, now: 5.6.16.