Hi Joel,
Thanks for the response.
After many hours of testing, I finally managed to get the template. I believe it's a combination of two things.
1. You have to be using the Common Data Service connector within your Data Integrator Connection Set. When you use the option to create a Connection within Data Integrator, the only connector type available for CDS is the Dynamics 365 connector. This won't work. Therefore, you have to create a Common Data Service connection before hand in the 'Connectors' area within make.powerapps. Once this is complete, your Common Data Service connection is available for selection within your Connection Set and you don't have to create one from there.
2. From what I can tell, it seems tenants in the UK data center are missing this template. Being UK based, most tenants I'm working on are in the UK data center. I created a new trial in the EU data center and the template appears. Would be interesting to see if someone else can validate this is the case.