A "soon to enter beta" online backup service, Bitcasa, claims to have both de-duplication (you don't backup something already in the cloud) and client side encryption.
A patent search yields nothing with their company name but the patents may well be in the pipeline and not granted yet.
I find the claim pretty dubious with the level of information I have now, anyone knows more about how they claim to achieve that? Had the founders of the company not had a serious business background (Verisign, Mastercard...) I would have classified the product as snake oil right away but maybe there is more to it.
Edit: found a worrying tweet : https://twitter.com/#!/csoghoian/status/113753932400041984, encryption key per file would be derived from its hash, so definitely looking like not the place to store your torrented film collection, not that I would ever do that.
Edit2: We actually guessed it right, they used so called convergent encryption and thus someone owning the same file as you do can know wether yours is the same, since they have the key. This makes Bitcasa a very bad choice when the files you want to be confidential are not original. http://techcrunch.com/2011/09/18/bitcasa-explains-encryption/
Edit3: https://crypto.stackexchange.com/questions/729/is-convergent-encryption-really-secure have a the same question and different answers