App is damaged and can't be opened

I'm now finding that signing an app seems to break it. I am running codesign on all the app's frameworks/libraries and the app itself without error, then creating a .dmg and running codesign on that too. I can open the resulting .dmg, drag the app to /Applications and open the app fine on my machine. But if I upload the dmg to my website and then another user tries downloading and installing it, I get the 'app is damged' error.

What's going on? How does one fix this?