Actually I do not see how one can still do dedup when dealing with ciphered data, and sadly I have no expertise on DropBox behavior, however since the edit section of the question shows some broader interest here is my two pence answer on how the above mentioned requirement could have been answered.
When a new account is created, a new ciphering key is generated, and this key is indeed stored along with the data but not in clear form : this key is ciphered using user's credential. Thanks to this:
The key cannot be found without finding user's password,
When the user changes its password, only the key needs to be re-ciphered with the new password, the key itself remaining the same the data does not need to be wholly re-encrypted.
When there is a requirement (legal, etc.) for some kind of management access over this data, the ciphering key will simply be stored twice, one protected by the user's key as described above, one protected using a secret known at higher management level only (using asymmetric encryption for instance, a server would have the possibility to cipher the key without storing enough knowledge to decipher it).
Such system can be regularly found to secure file storage like file systems and so on. Again, I do not know if DropBox applied this scheme or used any other method (and I doubt that DropBox will ever publish technical details about their internal security, at most some commercial speech).