A cloud computing platform and infrastructure for building, deploying and managing applications and services through a worldwide network of Microsoft-managed datacenters.
It seems we found the issue shortly after posting. You need to change the Advanced Settings for the policy so that it is aware of this.
You need to do the following;
Connect to the Compliance Powershell
Import-Module ExchangeOnlineManagement
Connect-IPPSSession -UserPrincipalName %username%
Get the current Label Policy Settings
(Get-LabelPolicy -Identity "Global").settings
Enable the Advanced Settings for AIP in the Policy
Set-LabelPolicy -Identity "Global" -AdvancedSettings @{EnableCustomPermissions="False"}
Set the AttachmentAction Advanced Setting to Automatic
Set-LabelPolicy -Identity "Global" -AdvancedSettings @{AttachmentAction="Automatic"}
Give it 10-15 mins and it will work.