Incredibly long execution time for a update query?
Your problem is simple
PROBLEM #1 : KEY DISTRIBUTION
The MySQL Query Optimizer evaluates the best course of action and publishes it in the EXPLAIN plan. Note that the EXPLAIN plan says selectType SIMPLE while using the index on the state. That is an index scan.
I have a basic rule-of-thumb I always go by : If an index has to read more that 5% of a table while perusing an index, it starts doing scans. You are basically at a tipping point. Why ???

205 rows to be updated
3504 total rows
5.85% of the table rows being read/updated

I am not just coming up with this. I have always mentioned this in the DBA StackExchange (Se my post from Nov 13, 2012 : Must an index cover all selected columns for it to be used for ORDER BY? and the other posts mentioned in it)
PROBLEM #2 : CONFIGURATION OF HARDWARE
The table is way too small to say it's just indexing. If the hardware you are using is small (1 vCPU), don't expect performance of any kind with MySQL 5.6. There are corner cases where MySQL 4.1 would outperform MySQL 5.6 in a single CPU environment. You are probably in that corner right now.
See my posts

Apr 26, 2012 : Is the CPU performance relevant for a database server?
Jun 19, 2011 : How do I properly perform a MySQL bake-off?

WHERE TO GO FROM HERE ...
You best bet at this point would be to run OPTIMIZE TABLE invoices;. This will shrink that table (eliminating fragmentation) and refresh the index stats. In a high-write production environment, you could run ANALYZE TABLE invoices; to refresh index stats only and run OPTIMIZE TABLE invoices; during a maintenance window.
Also, try setting up more that 1 CPU for test servers.
GIVE IT A TRY !!!