I had the same issue when using sybase, when two processes dead lock it just picks one at random and kills it.
There is another process running on the database that is competing for the resources which your process is after. This could be some maintenance process, or another connection trying to do something similar. Maybe sql server has some strategy for deciding which process to kill, if you could get it to kill the other one, then you could maybe find out more information about that one. I know with Sybase I could run the console and get fairly detailed information about the current lock status etc... and then I could identify where the fault was coming from. Find out if you can do that, if you can, then you can do some more detailed trouble shooting.
