Slower queries after upgrade from mysql-5.5 to mysql-5.6
The problem was that our new RDS instance was being throttled on writeIOPS, we could see queued disk operations (DiskQueueDepth of 10 or greater) and we could see writeIOPS averaging 300, whereas Amazon only provide 100 reliable iOPS (source).

The solution was to fork out approx $200 per month for "provisioned iOPS". 1000 is the smallest you could buy (which easily covers us). After this change which took 5 hours to complete on 350G of storage (but only 30s of downtime with a multi-AZ instance) everything was fine and our MySQL 5.6 instance was running better than the original MySQL 5.5 instance like all the literature promises. 

The problem was that the new RDS instance that we were given since migrating to 5.6 was just not as good as our original, which was just bad luck. We asked Amazon support "Q: Why would there be a difference in mysql5.5 than mysql5.6?"
From Amazon:


  Your previous underlying host may have been benefiting from unusually light use on the underlying volumes. You may have grown accustomed to very light use which allowed you to consume additional IOPs without accumulating as much DiskQueueDepth. However, when you moved to a new underlying host by upgrading you may now be experiencing more typical use of the underlying volumes. With typical use of the underlying volumes it's not recommended to consistently exceed the amount of reliable IOPs while expecting to maintain the lower DiskQueueDepth that you've grown accustomed to. However, there is no way to confirm or deny that this was the cause.