I'v encountered the same problems with a replication, When the publication was removed it didnt get totally deleted from the publication server. It all happend some time ago so I don't quite know anymore how I solved it, but I do remember that it made a difference how I removed the publication: by unchecking the database in published databases via the tools menu, or by removing the publication in the Replication tree from Enterprise manager
I think it is a glitch in SQL ...
I've come across this problem several times and I'm still not sure what causes it. Previously the only solution I had was to disable replication and re-create all the subscriptions (by scripting the replication before deleting it of course).
However the last time this happened I created a new subscription with the same name as the subscription that was causing the problem and SQL Server let me do it! If you then go on to delete the subscription that replication shows is in error and refresh replication, both the new subscription and the old one have gone and replication shows no errors!
What nuwins suggested worked!
I had a nasty red X in replication monitor for a publication that I had long ago deleted. So I just made a quick publication with the same name (it allowed me to do this!), and then the red X went away. Then I deleted the publication normally and the problem was solved!
Another solution for this will be cleanup table in MSDB.