Do you have traceflag 1222 enabled?

If so can you post the deadlock graph from the error log

If not run

DBCC TRACEON (1222, -1)

and then post the graphs once a deadlock has occured.