Error 1205 is indeed the deadlock error message. Update stats should not be able to deadlock with itself, as the only locks it takes are schema stability locks, and those are compatible with each other.
No chance anyone could have had any schema modifications running at the time? That's about teh only thing that should block a stats update.
Since you're on SQL 2008, you can pull the deadlock graph out of the system health extended events session. Post it here and we'll take a look.
Microsoft Certified Master: SQL Server, MVP, M.Sc (Comp Sci)SQL In The Wild
: Discussions on DB performance with occasional diversions into recoverability
We walk in the dark places no others will enter
We stand on the bridge and no one may pass