I think the problem stems from the fact that I installed the program for all users from another account, so the permissions were all wonky and wouldn't save the new xattr. Here's the solution:
$ cd /path/to/application
# View all files with extended attributes
$ ls -lsa
# To see the files that are quarantined:
$ xattr -l * | grep com.apple.quarantine
# Remove the extended attributes
$ sudo xattr -d com.apple.quarantine \
$(xattr -l * | grep com.apple.quarantine | \
awk -F: '{print $1}')