Those were/are publicly available in a multi-GB download around the net.

It seems they must have, unless Facebook brute-forced or otherwise obtained the key which the database used to encrypt (two-way encryption, big no-no) the passwords.

Based on this article it's not immediately obvious how Facebook checked/knew that the password was in the pile, as opposed to just the user's email address. I'd think this means either they were given the encryption key by Adobe, Adobe simply gave them the plaintext keys, or they managed to get the key themselves (if it was weak).

Ninja edit: It appears there are sophisticated ways of figuring out the passwords without getting the key, and this is mentioned briefly in the bottom of the OP article. Also, this is the source for that info [0]

[0] http://nakedsecurity.sophos.com/2013/11/04/anatomy-of-a-pass...