MySQL UPDATE Performance Issue
What does EXPLAIN show for that query?  What does mysqltuner show? What does free -m show?

If turning the query cache off helped, I'd suspect you are running out memory and your machine is starting to swap.  Swapping is a pretty effective way to kill MySQL's performance.  The solution would be to either increase the memory of the machine, or tune MySQL to require less memory.