ERROR: relation "xxx" already exists but where????

I managed to drop a table without apparently droppig it's primary key
After recreating the table I try to recreate the primary key.

If I run the following:

ALTER TABLE case_histories
  ADD CONSTRAINT case_histories_pkey PRIMARY KEY(case_history_id);

Postgresql responds with:

NOTICE:  ALTER TABLE / ADD PRIMARY KEY will create implicit index "case_histories_pkey" for table "case_histories"

ERROR: relation "case_histories_pkey" already exists
SQL state: 42P07

The table does not have this key. Assuming that the response is correct, where can I find and/or delete this relation?
Ihave deleted an entry inpg_constraint with that name but that did not do the trick 

TIA

Joost

Joost