Parallel transactions failing oddly

Hi,

Either we have found a bug in Postgres (which I seriously doubt) or we
are being stupid clever enough way to not notice it.

We have five complex "transactions" that are executed thru pq++/c++
interface. If we run them one by one everything goes fine. But if I
run them in parallel - in separate processes - all but the first one
claiming the lock for "ryhmalaiset"-table will fail. And they will
fail as soon as the first one is finished by trying to insert
duplicate row in the shared table. Incidentally this row would also be
the very first row they are trying to insert. They all run the same code
but with different data.

Each transaction fails in the following insert:
 LOOP
  SELECT * INTO r FROM kelaaryhma(aToimiala, aKielikoodi, pKoodi);

  SELECT INTO pRyhmalaiset * FROM ryhmalaiset
  WHERE
          toimiala      = aToimiala             AND
          ryhma         = pKoodi                AND
          kuukausi      = aKuukausi             AND
          vuosi         = aVuosi;

  IF NOT FOUND THEN
          aMessage:= pKoodi::VARCHAR(16)||''/''||aKoodi::VARCHAR(16);
          RAISE NOTICE ''ins-ryhmalaiset %'', aMessage;
          INSERT INTO ryhmalaiset
              (toimiala, ryhma, jasen, kuukausi, vuosi, ajettu)
            VALUES
              (aToimiala, pKoodi, aKoodi, aKuukausi, aVuosi,
               ''now''::timestamp);
  END IF;
...

Where (toimiala, ryhma, kuukausi, jasen, vuosi) are primary index
fields. The "IF NOT FOUND" should ensure that no duplicate inserts are
attempted but somehow it just fails when two or more processess are
run.

Without lock on "ryhmalaiset" only some of the transactions will fail
and some will not.

Any ideas what we are doing wrong?