It looks as if the Terminal app was removed and replaced with an application that displays that dialog, so changing permissions won't help. Doing a clean install as BaronVonKaneHoffen suggested would work, but there are another options.
Option #1 - Restore from another Mac
If you own or have access to another Mac, you can copy /Applications/Terminal.app to /Applications/Terminal.app on this mac.
Option #2 - Restore from the Recovery Partition
(Almost?) Every Mac has had a recovery partition since Mac OS X Lion. If you turn off your computer and turn it back on while holding Command + R as described in https://support.apple.com/en-us/HT201314 you will enter the Recovery Partition. From there, you can select Utilities->Terminal to enter the Terminal. From there, you can type in (untested, something like this)
cd /Applications/Utilities
rm -rf /Volumes/Macintosh\ HD/Applications/Utilities/Terminal.app
cp -r Terminal.app /Volumes/Macintosh\ HD/Applications/Utilities/Terminal.app
Option #3 - Restore from an Apple Software Update
This is the easiest way as it can be done without rebooting or transferring files. Simply download a Terminal replacement such as iTerm (Heck, you might as well just use that instead of Terminal) and run
cd /tmp
rm -rf TERMINALRESTORE
mkdir TERMINALRESTORE
cd TERMINALRESTORE
curl -ORL http://swcdn.apple.com/content/downloads/21/09/031-20634/8d84o1ky5gn2agnf5kiz9eed134n7y3q4c/RecoveryHDUpdate.pkg
xar -xf RecoveryHDUpdate.pkg
hdiutil attach -nobrowse RecoveryHDMeta.dmg
hdiutil attach -nobrowse "/Volumes/Recovery HD Update/BaseSystem.dmg"
sudo rm -rf /Applications/Terminal.app # Erase the old Terminal app. Password required.
sudo cp -Rp "/Volumes/OS X Base System/Applications/Utilities/Terminal.app" /Applications/Utilities/Terminal.app # Copy over the new Terminal app
hdiutil detach "/Volumes/OS X Base System"
hdiutil detach "/Volumes/Recovery HD Update"
cd ~
rm -rf /tmp/TERMINALRESTORE
Additionally, you can simply run curl https://gist.githubusercontent.com/lights0123/2a03d88f99fbbdfc8a35/raw/8d961db047d387319e07e56c228847394ecc1b57/Terminal.command | sh
to avoid copying/pasting the above.