This error indicates that the mailing has been used on the exclusion tab in the Previous mailing exclusions section.  Once the mailing has been deleted from this section, then you can delete the unwanted mailing.