Is this sql server 2005? Then run a profiler and capture the deadlock graph. Deadlock can occur because of a lot of reasons and the deadlock graph will give you a good idea where to start.
Also, just an observation. Most of the times while resolving deadlocks,we tend to look for X locks only. But please do examine the S locks also and let us just remember that a deadlock occurs on one (or more) resource. That resource can be a table itself, a row, a page, an index anything.
Even a simple select and then and update statement may lead to a deadlock.
So best idea would be to get hold of the deadlock graph first and then only can this problem be solved