They can dedupe without needing to decrypt. Tarsnap does this. The issue is with features like being able to reset your password, downloading and sharing files via the web interface, etc.
Dropbox dedupes across users, if Alice and Bob both upload foo.txt with identical contents (but encrypted with their own keys) the encrypted result will not be identical even though the files are. Right now Dropbox does dedupe in this situation, which obviously required unencrypted access to both files.