Relation n does not exist when trying to ad a foregin key

Dear all:

I am having this error when I try to add a foreign key:
ERROR: Relation n does not exist

Here is the command:

test=# alter table cep_bairro add FOREIGN KEY (cod_localidade) REFERENCES
cidade (cod_localidade);

NOTICE: ALTER TABLE will create implicit trigger(s) for FOREIGN KEY
check(s)
ERROR: Relation 107890740 does not exist

On the other hand, the same command works for another table, when I try to
link to the same table:

test=# alter table cep_logra add FOREIGN KEY (cod_localidade) REFERENCES
cidade (cod_localidade);

NOTICE: ALTER TABLE will create implicit trigger(s) for FOREIGN KEY
check(s)
ALTER TABLE
Time: 234175.99 ms

What is is going?

These 3 tables (cep_bairro, cep_logra and cidade) where changed a lot,
either by being recriated or via alter table.

Table cidade has its primary key changed, but both related tables
(cep_bairro, cep_logra) have their corresponded field also changed.

Thanks.