Also, if I wanted to know if you had a specific file (and I had access to all your encrypted files) this would be trivial, correct?
Yes, but that's no different from keeping any other kind of directory structure. And you can apply the same trick to the directory structure itself, so all you really need to keep is a "root hash" to your (encrypted) directory.
> Also, if I wanted to know if you had a specific file (and I had access to all your encrypted files) this would be trivial, correct?
What do you mean by "I had access to all your encrypted files"? If you've broken in to the server, everything is encrypted, including the directories. The only thing you can tell is whether a particular encrypted block corresponds to data that you already possess (or possessed at some time in the past). But that by itself tells you nothing.
http://www.ssrc.ucsc.edu/Papers/storer-storagess08.pdf
TL;DR version: take a chunk of data, encrypt it with its own sha1 hash as the key. Now you have an encrypted version that you can dedup. You can only decrypt if you already know the hash. Info about who owns any particular chunk is not kept on the server, so even if you break in to the server, all you can tell is which chunks correspond to data you already possess. Seems plausible.