Hello Cam,
Good day! Thank you for posting to the Microsoft Community. We'll be happy to help!
First of all, please accept my apologies for the inconveniences caused, issues like these can be frustrating.
Based on your description, I understand that you after assigning the license that includes Teams phone system, the enterprise voice is not enabled automatically.
Indeed, as you mentioned, when you assign a license that includes Teams phone system the enterprise voice should be enabled automatically. below are some things to check:
Correct License: Please check and confirm that the Microsoft 365 Phone system is enabled, for that user after assigning the license, you can do it by following below steps:
Go to 365 admin center > Users > Active users > User you want to assign the license to (or user who have the license) > Go to the licenses and apps tab > Scroll down, and expand Apps > Chack and confirm if Microsoft 365 Phone system is enabled:


Propagation Time: Please note that after assigning the license, it can take up to 24 hours for the changes to propagate. (May I know if the issue still occurs even after 24 hours).
If Microsoft 365 Phone system is/was enabled and you have been waiting for up to 24 hours, and the issue persists, I highly recommend contacting Microsoft technical support team, to investigate why enterprise voice is not being enabled automatically as it should.
Another thing that might be causing this might be the way the users are being provisioned ("After a user is created they automatically get assigned an E5 license"), the Teams can check on this as well.
Microsoft's back-end support team can have a remote session with you to check the issue and collect/inspect the advanced logs and investigate the cause of this issue from the back end.
Due to the limited permissions and access resources of our community moderators, and the privacy of your data, we are unable to collect certain types of logs in public forums.
Submit a service request: Global admins can create a service request with Microsoft Support for advanced technical assistance and diagnostics. For detailed instructions on how to get support, see Get support - Microsoft 365 admin | Microsoft Learn
Call Microsoft Support: For more help, use this link to find the appropriate contact number: Find Microsoft 365 for business support phone numbers by country or region - Microsoft 365 admin | Microsoft Learn
Thank you very much for your cooperation and understanding.