One common cause is if you have your instance connected to a CRM and you have the delete flag set to "Delete from CRM = Yes" but the sync user doesn't have permission to delete leads in the CRM. The error should be listed in the activity log of the leads you tried to delete.
As Nicole stated, support can give you a more precise answer.
This indicates that Marketo doesn't have permission to delete Leads or Contacts in your CRM. Please check with your CRM Administrator, if they can grant Marketo the permission to delete Leads and Contacts.