Lewis,

My first thought (without testing) is that trigger might be causing some of your problem. If you have a sandbox / dev server, try disabling the trigger then running your update statement to see if that makes a difference.

In the meantime, we'll all be diving into your code & execution plan to see what else we can find.