de-duplication is the process where if two customers both store the same file, say abbey_road_from_itunes.mp3 the service provider only needs to store one copy of it. They can't do this if they encrypt each copy of that file individually for each customer. This adds up to a lot of space for a service like this, as most of the large files people store aren't their own creations.

An identical file encrypted with key X will be a different blob from one encrypted by key Y. About the best you can do is slice the file into N byte blocks and dedupe on that (this is what some modern filesystems like ZFS do).

De-duplication requires verifying that two files are identical. If they can verify that two files are identical they either compared them both in unencrypted form or they can compare the two encrypted files. The first method would require them to be able to unencrypt files without prompting all users for their private key to compare the copies.

The second method would require identical files from different users to encrypt to the same form, meaning the encryption is not key dependent and thus can also be decrypted without your key.

There may be some other method I'm missing but I don't see how they could de-duplicate with key-dependent encryption when their users hold their own keys.