When a User policy is updated to allow Teams recording it does not always get applied for users. The Team Call recording toggle within the Application Settings should be toggled ON as shown below:
Latest update and guidance
This issue is being investigated under PRB0172508.
The Teams Call Recording setting can be set manually via the User policy which will push through the Teams Call Recording setting update.