If stats are out of date, the query optimizer is more likely to make a poor choice of execution plan.  The query will take longer to run and deadlocks will become more likely.  You'll want to have a look at the actual queries that are causing the deadlocks to see whether they can be tuned to make them more resilient to this situation.

John