I stuggled with this issue and wasn't able to resolve with the many
possible solutions posted. After a bit of tweeking I resolved our
issue as follows:
SQL DB Maintenance plan is successfully performing backups but fails
to remove old backup files as configured in the plan. Disk space is
sufficiant. Plan script verifies. Deleting and recreating the plan
does not resolve the issue.
Verify that the recovery model on master and msdb db is set to Simple.