In my case the problem was I had created some manual backups without any file extension in the backup directory, this meant that the maintenance plan could not create directories with the same name.
So check what could be preventing the creation of files or folders, check permissions, check which user the sql agent is running as.