I created a new relationship type, and then immediately removed it, and it worked just fine. Evidently, that relationship type must have still been in use. If you still have that data around, let me know on IRC and I'll explain how to get a better bug report.

I still can't remove the "covers and versions" work-work relationship type.

I now also can't remove the "score" release group-url relationship type (the proposal to remove it passed).

My replicated database is showing no relationships for these two:

musicbrainz=# select lww.entity0 from l_work_work lww, link l, link_type lt where lww.link=l.id and l.link_type=lt.id and lt.name = 'covers and versions';
entity0
---------
(0 rows)

musicbrainz=# select lrgu.entity0 from l_release_group_url lrgu, link l, link_type lt where lrgu.link=l.id and l.link_type=lt.id and lt.name = 'score'; entity0
---------
(0 rows)

musicbrainz=#

Ok, the problem is link rows exist, but they don't have any l_release_group_url rows. So as far as you're concerned, the relationship doesn't exist, but as far as the admin system is concerned, there are relationships in existance. The review at http://codereview.musicbrainz.org/r/1584/ should sort that out, by removing these redundant link rows and ensuring they never exist.