$ xattr -l /Applications/Firefox.app ... com.apple.quarantine: 0000;51...|com.apple.SafariClearing it did the trick:
$ xattr -d com.apple.quarantine /Applications/Firefox.app
UPDATE: Recently started receiving a similar error when opening a certain app:
You are opening the application "foo" for the first time. Are you sure you want to open this application?
Resolved using kopischke's advice:
/System/Library/Frameworks/CoreServices.framework/Versions/A/Frameworks/LaunchServices.framework/Versions/A/Support/lsregister -kill -r -all local,system,user
/mac | Feb 11, 2013
Subscribe or visit the archives