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