I had this error when trying to use directories on the backup server. If this is your case then don't use directories, upload all backups to the root directory.
I know that's not ideal, we want to keep clients' backups seperate, but it's all we can do for now. It's an ovh issue, not plesk. For now run periodic backups of the full server and restrict client access to the backup server. Restore by request. When you copy a backup from ftp to your server repository each client will get access to their site backups made as part of the full backup.
It is progress though, before plesk 12.5 we couldn't even link clients' accounts to the ftp backup storage.