Значит так, все получилось.
Методом проб и ошибок выяснилось, что виноват во всем файл storage_service_s3.php
Я посмотрел в ошибках хостинга, что выскакивает когда бэкап не уходит облако. Там нашел следующее:
[fcgid:warn] [pid 25222] mod_fcgid: stderr: PHP Fatal error: Call to undefined function hash() in .../bitrix/modules/clouds/classes/general/storage_service_s3.php on line 204
Пошел по пути возникновения ошибки. Нашел этот файл storage_service_s3.php. Он оказался большим и трогать я его не стал. Нашел старый бэкап, кажется январьский, и скопировал только этот файл в систему. Все стало нормально уходить в облако. Правда с третьего раза. Сначала 500 ошибку выдало, потом чего-то БД не считались, с третьего раза все ушло в облако.
Посему, брат, ищи старый файл storage_service_s3.php и кидай его .../bitrix/modules/clouds/classes/general/ и все должно работать.
P.S. Если что, могу выслать свой фал, если у себя не найдешь. Напиши только куда, через ЛС
____________ (спустя ночь)
P.S.S. Ночью сдедалось резервное копирование по расписанию и ушло в облако, без каких-либо проблем. Ошибка связана с обновлениями и конкретно с обновлением этого файла... по крайней мере у меня. Написал разработчикам, пусть ищут свою ошибку.