Unable to restore TDE enabled database when MAXTRANSFERSIZE and CHECKSUM is used

I was able to reproduce your problem.

Adding FORMAT to the BACKUP command solved it for me.

While I can't seem to find concrete documentation, it's my opinion that this is related to the fact that INIT retains the existing media header on the backup set while FORMAT creates a new media header.

I'm still researching this issue and if I find additional information, I will update this answer.

Seems like this might have been addressed with KB 4032200:

• FIX: Fail to compress the backup file when INIT and COMPRESSION option is used in a TDE enabled database in SQL Server 2016

From that entry:

Symptoms

Assume that you enable Transparent Data Encryption (TDE) for a database in Microsoft SQL Server 2016. You try to backup the database by using the BACKUP DATABASE T-SQL statement that has both COMPRESSION and INIT option specified. In this scenario, you may notice that the existing backup file is overwritten by the new backup file, and the new backup file is not compressed.

Resolution

This issue is fixed in the following cumulative updates for SQL Server:

• Cumulative Update 7 for SQL Server 2016 RTM
• Cumulative Update 4 for SQL Server 2016 SP1