Deadlock Error from SQL Server 2000 to SQL Server 2008
After upgrading to SQL Server 2008, did you run the below?


DBCC UPDATEUSGAE 
UPDATE STATS WITH FULLSCAN
REBUILD ALL INDEXES


The statistics blob is changed significantly from 2000 to SQL Server 2008 and the above steps are very important after the upgrade. I have seen many ppl run into performance problems but not deadlocks. I would try doing all of the above if you haven't so far and try to reproduce the problem afterwards.

That said, what is the results of SELECT @@VERSION on the 2008 box? Are you updating one row or several rows?