Does changing the TDE Master Key always require decryption and re-encryption?
The DB Master Key and/or the DB encryption key.
The main two secrets involved in TDE are the Database Encryption Key (DEK) and the Server Certificate. The DEK is what actually encrypts and decrypts the data in the database, but the Server Certificate is used to protect (among other protections already involved) the Database Encryption Key (DEK).
To your question, If you rotate the DEK you must decrypt and encrypt all data in the database because it is the key which does this.
If, however, you rotate the Server Certificate protecting the DEK, then no data encryption or decryption of the physical database would need to take place.
It doesn't matter the version or type of software, if you encrypt data with an asymmetric key pair and want to rotate to another asymmetric key pair, you'll first need to decrypt the data with the old set of keys and encrypt it with the new.