I think the idea is that you should be able to reconstruct the data fully from any X of Y configured shards of the data (and keys). You can do this with multi-signature keys and reed-solomon codes for the data. There may be some smart way to combine the two that exists. Anybody know of an algorithm that would accomplish this? I vaguely remember reading a paper using Goppa codes that worked likes this, but google-fu is failing this morning.

Just use regular Reed-Solomon for the data and Shamir's Secret Sharing for the key (an implementation is for example http://point-at-infinity.org/ssss/).

If you choose the same parameters for both algorithms, you can freely assign any key with any data shard and store those.