Backup to URL not working when using Ola Hallengrens Database Backup
I just ran into this issue as well creating a Maintenance Plan in SQL Server. The default backup maintenance plan creates a script that includes WITH CREDENTIAL, but I was able to get it working when I removed that default Task. So I ended up with this code in an Execute T-SQL Statement Task:

declare @backuptime as varchar(250);
set @backuptime = 'https://youraccountname.blob.core.windows.net/backups/mytestdb_' + CONVERT(VARCHAR(19), GETDATE(), 120) + '.bak';

BACKUP DATABASE yourdb   
    TO URL = @backuptime