Is there anything else I need to do get the backups working?
Enabling Geo-Redundant Backup Storage (GRS) for an Azure SQL Database eliminates the need for extra manual measures to guarantee the creation and functionality of backups. Azure SQL Database automatically manages backups
Azure SQL Database automatically performs backups of your database without requiring any intervention.
I tried the same in my environment and got first backup in few minutes:

I take few minutes to create the backup.
Check you have SQL DB Contributor or SQL Server Contributorroles assigned to you in azure server.
Check if you have below permissions:
| Permission | Access level | Use case |
|---|---|---|
| Microsoft.Sql/locations/longTermRetentionBackups/read | Read | To list the long-term retention backups for every database on every server in a location. |
| Microsoft.Sql/locations/longTermRetentionServers/longTermRetentionBackups/read | Read | To list the long-term retention backups for every database on a server. |
| Microsoft.Sql/locations/longTermRetentionServers/longTermRetentionDatabases/longTermRetentionBackups/read | Read | To list the long-term retention backups for a database. |
I cannot see any 'Recovery Services vaults' in our Azure account. Is this necessary for backups?
No, Recovery Services vaults is not Require for Azure SQL backup. SQL Server database that's running on an Azure virtual machine (VM) that will get backed up to an Azure Backup Recovery Services vault.
If all configurations are correct but backups are still not visible, then you can contact Azure Support to further investigation.