foreign keys and deadlock

hi,
i've got several tables, say table A and others. there are foreign keys in
table A referencing columns in the other tables. i've got 2 processes
running simultaneously: process P and Q. P inserts rows into table A. Q
updates inserted rows in table A. i'm seeing errors deadlock detected. i
discovered from the logs that last thing process Q did before deadlock is
one of the "select oid from only for update" checking the foreign keys
constraints. what was exactly the last query executed by process P i don't
know because in the log there is only select insert_into_A() and not the
queries inside the function (why? i have turned query_logging on and i can
see the subqueries from other functions...). i think that this may be a
foreign key issue because when i removed all foreign key constraints
everything works fine (i know this is not a proof but when using foreign
keys deadlock is reported sooner or later each test run with certain
settings but i have never saw it with foreign keys removed and any
settings yet...). is it possible that the deadlock is caused by the
foreign keys checking in these two simultaneous transactions?  any other
ideas?

thank you,

kuba

more details:
(hope didn't oversimplify it and eliminated the real cause...)

table A has columns id, state, and fkey1,fkey2,...
processes P and Q are the only 2 processes accessing this database.

process P pseudo-code: (written in delphi, using odbc)
  while (1) {
    begin work;
    getNext(id, fkey1, ...); - not database function...
    select insert_into_ A(id, 0, fkey1,...);
    commit work;
  }

pl/pgsql insert_into_A(...) inserts row into table A

process Q pseudo-code: (written in C using ecpg)
  while (1) {
    open cursor for select * from A where state=0 on conn1;
    while (not empty) {
      fetch into id...;
      begin work on conn2;
      select update_A_set_state_1(id) on conn2;
      commit work on conn2;
    }
    close cursor;
  }

pl/pgsql update_A_set_state_1 updates one row in table A.

i'm using pg 7.1.3 installed from debian package.