What does Bitcoin-Qt "Change Passphrase..." do to existing private keys and corresponding addresses?
The wallet actually uses a randomly generated master key to encrypt the keys, and this master key is encrypted using your passphrase.

When you change the passphrase, all that changes is the encrypted master key. The actually encrypted wallet keys aren't touched at all.