Integrity violation when adding foreign key constraint

I hope somebody can help me with a question. I have two tables

  CREATE TABLE sk (
    fnr INTEGER,
    knr SMALLINT,
     [...]
    CONSTRAINT sk_pk_fnr_knr PRIMARY KEY ( fnr, knr )
  );

  CREATE TABLE sg (
    fnr INTEGER,
    knr SMALLINT,
    gpc CHAR(1),
     [...]
    CONSTRAINT sg_pk_fnr_knr_gpc PRIMARY KEY ( fnr, knr, gpc )
  );

loaded with data. When I try to add a foreign key constraint with

  ALTER TABLE sg ADD CONSTRAINT sg_fk_fnr_knr FOREIGN KEY ( fnr, knr )
    REFERENCES sk;

I get the error message

  NOTICE:  ALTER TABLE ... ADD CONSTRAINT will create implicit trigger(s) for
           FOREIGN KEY check(s)
  ERROR:  <unnamed> referential integrity violation - key referenced from
                    sg not found in sk

But when I try to find the offending row(s) in sg with

  SELECT * FROM sg WHERE NOT EXISTS ( SELECT * FROM sk WHERE
    sk.fnr = sg.fnr AND sk.knr = sg.knr );

I get nothing (0 rows).

This is PostgreSQL 7.0.3 on BSD, and I ran vacuum analyze on both tables
first.

Am I doing something wrong, or what might be a reason for what looks
like a contradiction to me? Foreign keys on multiple columns work like
this, don't they?

Kind regards,
Daniel