So is it true the uncompressed keys must be used? I'm also trying to reproduce what bitcoind's multisig implementation does, and am getting a different output address using compressed keys.
As others said, check the order of your keys. It matters - different order will output a different address.