Without knowing the exact DDL, I'm guessing that adding yet another index won't help the update speed. I think the update is slow because you are getting page splits while updating the long varchar column.

As an aside, can you control the behaviour of varchar(max) so it is stored only in LOB pages?