This is a problem caused by Mac OS X's GateKeeper setting.
Gatekeeper is a new feature in Mountain Lion and OS X Lion v10.7.5 that builds on OS X's existing malware checks to help protect your Mac from malware and misbehaving apps downloaded from the Internet.
This article is related to what you are experiencing.
This solution from minecraft.net seems to work for most people:
If you see a warning on Lion and above reading "Minecraft" is damaged and can't be opened. You should move it to the trash.", you have to set Gatekeeper to allow Minecraft as it is not yet certified as coming from a known developer.
There are two ways:
in System Preferences > Security & Privacy:
Set "Allow Applications Downloaded From" to 'Anywhere'.
You have to click the lock on the bottom to make changes. Once you start up
minecraft.app , you can change it back to 'Mac App Store and identified developers'.
A different way is to right-click
minecraft.app and click open. You will be asked for confirmation.
If the above doesn't work, try this first:
This will allow your minecraft.app to run:
chmod +x ~/Desktop/Minecraft.app/Contents/MacOS/JavaApplicationStub