@Jay Thanks for your question. I did a quick check at my end and I was able to call the cmdlet 'New-CsTeamsComplianceRecordingPolicy'.
You have mentioned that you have installed the version 2.3.1 of Microsoft Teams. First thing would be check the possibility of multiple versions of the module being installed. Recommend you to Run the below command, you will see all the Modules with MicrosoftTeams
Get-Module *Teams* -ListAvailable
If you see multiple versions - request you to remove all the older versions .
Uninstall-Module MicrosoftTeams -RequiredVersion 1.1.6
Now, you could freshly import the Microsoft teams module
If there is just one version - 2.3.1 - there could be a possibility of corrupt installation. Please uninstall the MicrosoftTeams and reinstall the module.
Install-Module MicrosoftTeams -RequiredVersion 2.3.1
Also , check whether the command is existent by running
Get-command New-CsTeamsComplianceRecordingPolicy .
Once you confirm similar output at your end, try running the cmdlet.