Deadlock with ShareLocks?

I've an interesting error with deadlocks on a quite simple table:

Version:     8.1
Query        : update last_modified set dataend=now() where type='list'
DB-Error     : ERROR:  deadlock detected
DETAIL:  Process 10454 waits for ShareLock on transaction 1347632; blocked by 
process 15920.
Process 15920 waits for ShareLock on transaction 1347633; blocked by process 
10454.

I thought ShareLock is not really blocking, or am I wrong? The bad thing is, 
that it's quite difficult to get the info what the other backend was doing at 
the same time. Maybe it would be a good idea to log the statements of both 
backends (if available). Would make detecting such errors quite easier.

Best Regards,Mario Weilguni