Until this problem is fixed by Automic, we run this additional command whenever installing the AE DB Utilities — after the programs have been extracted from the .tar.gz file, but before they are used the first time.
$ chmod a+x ucyblgmx ucybdbrt ucybdbrr ucybchng