Postgres locking

I'm trying to use select for update locks in Postgres.  When I do this:
  begin work;  select data from table where key = 1 for update;

in two psql's running simultaneously, about half the time the second 
transaction blocks and waits for the first to end (which is what I want 
it to do), the other half the time I get this:
  ERROR:  XactLockTableWait: LockAcquire failed

and the transaction is aborted.  I can't find any pattern, if I do the 
same statements in the same order several times, it will be block one 
time and error the next apparently at random.  I also tried using LOCK 
TABLE and found the same basic problem, sometimes the second 
transaction will block, other times it will abort with:
  ERROR:  LockRelation: LockAcquire failed

Do I have a configuration problem?  Is this a bug in Postgres?  I'm 
still running 7.2.1, would upgrading to 7.3 fix this?

Thanks!

Bob Smith
Hammett & Edison, Inc.
bsmith@h-e.com