It is difficult to determine the exact cause for the dead lock without knowing the data that is being passed in.
I have created a small scale sample with your DDL and some test data and successfully updated the table, so I believe your update is fine and the problem may be the transaction isolation level and/or another spid has a lock on the table.
What is your transaction isolation level? It looks like there is another connection attached to the table that is blocking your update. While running the update have you gone into activity monitor and seen if the process is being blocked? In Activity monitor there is a column "blocked by."
Is it possible that the update has an explicit begin transaction and does not have a commit?
Additional info on isolation levels: