Foreign key error...

I'm adding foreign keys to some exixting tables that reference and master
key table as outlined:

CREATE TABLE public.clientinfo
(
  clientid int4 NOT NULL DEFAULT nextval('seq_clientid'::text),
  caseid int4 NOT NULL DEFAULT nextval('seq_caseid'::text),
  clfirst varchar(30),
  ...
  CONSTRAINT clientinfo_pkey PRIMARY KEY (caseid)
) WITH OIDS;

Now...the following table allowed the creation of a foreign key:
CREATE TABLE public.debts
(
  debtid int4 NOT NULL DEFAULT nextval('seq_debtid'::text),
  caseid int4 NOT NULL,
  debttype varchar(20),
  ...
  CONSTRAINT pk_debts PRIMARY KEY (debtid),
  CONSTRAINT fk_debts FOREIGN KEY (caseid) REFERENCES public.clientinfo
(caseid) ON UPDATE CASCADE ON DELETE CASCADE
) WITH OIDS;

The following tabel did NOT allow the creation of a foreign key:
CREATE TABLE public.casenotes
(
  noteid int4 NOT NULL DEFAULT nextval('seq_casenotes'::text),
  agentid int4 NOT NULL,
  caseid int4 NOT NULL,
  ...
  CONSTRAINT pk_casenotes PRIMARY KEY (noteid)
) WITH OIDS;

The command I attempted to execute was:
alter table casenotes
add constraint fk_casenotes foreign key (caseid) references
public.clientinfo (caseid) on update cascade on delete cascade;

The error returned was:
ERROR: fk_casenotes referential integrity violation - key referenced from
casenotes not found in clientinfo

Why will it work on some tables and not others?  The "failing" table was
created in the same manner as the others.

Any ideas?

Thanks,
Derrick