... for those interested I have a solution.

After looking in the Distributor database and in particular the table MSsubscriptions, I found records with the subscription name of the subscription I had deleted.

Once I deleted these records, I was then able to recreate both the publication and subscription and all is working fine.