Well, we will probably never be completely sure as we don't have the code. But we can discuss some possibilities. But first,
Why the change, actually?
What could be a reason for this change anyway? A possibility is that intelligence agencies had something to do with this, like is assumed to have happened with an older version of A5/1, Comp128v2, where the first ten bits of a 'random' key were always set to 0. Like this they can, if they get the hash from MS, just brute-force faster.
In case you don't like complot theories, another option is of course that MS doesn't want you to forget your password.
But let's look at the possibilities.
Passwords stored in plaintext
It is possible that MS stored plaintext passwords, but it would be a huge failure and I suppose (and truly hope) this is not the case.
Normally passwords are hashed and salted in an irreversible way so that even MS can't get to know your password from the value in the database. So how did they do this?
Two versions of a hash function stored parallel
What would be a possibility is that they already planned for longer time to have a maximum length on the password. Then, they could wait for you to login and, parallel to checking if you're actually typing in the correct password and logging you in, cutting off your input and salting and hashing that and store it somewhere else. At the moment they changed to the new system, they just copied the new hashes.
The passwords were always 16-chars truncated
As pointed out by Ajedi32 in the comments, it's also a possibility the passwords were always truncated after 16 characters already. (The reason for this, again, could be interference by intelligence.) The only difference is that MS now doesn't allow you to enter more, because they've become too lazy to truncate it themselves.
This doesn't seem likely to me, because if this were true, then why would they now tell the users to not enter more than 16 characters? Yes, it could be that things like this (i.e. UI texts are changed without an actual change of the function) just happen in a huge organization. However, as Ajedi32 explains:
Maybe they finally realized that not telling users about such an important security limitation was a bad idea, and decided to start explicitly enforcing the 16-character limit? Or perhaps they're preparing to lift the limitation in the future, and they need to start preparing users for that now? (Because lifting the limitation would mean that "1234567890123456" would no longer be the same password as "1234567890123456789")
The actual answer
As it turns out, Ajedi32 was right and passwords were always truncated, as pointed out in this MS article (credits go to PwdRsch, see the comments). The other possibilities remain here for theory's sake.