Newly created Azure App Service can't connect to existing Azure SQL Database

I created a new Azure App Service to test out staging. I deployed my existing application to it but it seems it can't access the already existing database. I always get this exception:

Microsoft.Data.SqlClient.SqlException (0x80131904): A network-related or instance-specific error occurred while establishing a connection to SQL Server. The server was not found or was not accessible. Verify that the instance name is correct and that SQL Server is configured to allow remote connections. (provider: TCP Provider, error: 0 - No such host is known.)
 ---> System.ComponentModel.Win32Exception (11001): No such host is known.
   at Microsoft.Data.ProviderBase.DbConnectionPool.CheckPoolBlockingPeriod(Exception e)
   at Microsoft.Data.ProviderBase.DbConnectionPool.CreateObject(DbConnection owningObject, DbConnectionOptions userOptions, DbConnectionInternal oldConnection)
   at Microsoft.Data.ProviderBase.DbConnectionPool.UserCreateRequest(DbConnection owningObject, DbConnectionOptions userOptions, DbConnectionInternal oldConnection)
   at Microsoft.Data.ProviderBase.DbConnectionPool.TryGetConnection(DbConnection owningObject, UInt32 waitForMultipleObjectsTimeout, Boolean allowCreate, Boolean onlyOneCheckConnection, DbConnectionOptions userOptions, DbConnectionInternal& connection)
   at Microsoft.Data.ProviderBase.DbConnectionPool.WaitForPendingOpen()
--- End of stack trace from previous location where exception was thrown ---

But the connection string is correct in the settings and correctly loaded. I thought it might be, that I have to open the firewall on the database to the new service. But on the database server the setting is already activated to give all services access.

All Services are in the same Resource Group. And I can't see any difference in the App Service settings. Do I have to enable something explicitly somewhere?

EDIT: I copied an existing app service and deployed to that. Here I can access the database server of the service I copied, but not the second one. So I presume I have to adjust a setting somewhere to enable that.

In the end I wrote the support and together with them I just created a new database server and copied the database over. That way it worked.