I scratched my head for quite some time until I had a better look at the actual connection string. The server name was correct as well as the database name and security configuration. For example:
At first I didn't notice the "Provider" part, but then I decided to strip the connection string to the bare minimum, and try again.
Data Source=.;Integrated Security=SSPI;Initial Catalog=MyDatabase_Warehouse
Surprisingly, it worked right away. But I honestly have no idea why it does not work if you specify the provider.
Maybe it is related to differences with the SQL client version installed on the machine that generated the package, but I have no time to further investigate.
EDIT: Apparently it was related to the fact that I selected the "Native OLE DB > SQL Server Native Client 11.0" provider instead of ".Net Providers > SqlClient Data Provider" in the connection string of the datasource in the SSAS project. After selecting the correct provider and rebuilding the package, everything worked as expected.