OS is Centos 7.3.
Seems to be an Selinux issue:
./audit.log.1:type=SYSCALL msg=audit(1496116026.926:2397544): arch=c000003e syscall=263 success=no exit=-13 a0=ffffffffffffff9c a1=b4e0c0 a2=0 a3=7fff193746a0 items=0 ppid=10217 pid=11042 auid=0 uid=0 gid=0 euid=0 suid=0 fsuid=0 egid=0 sgid=0 fsgid=0 tty=(none) ses=68974 comm="rm" exe="/usr/bin/rm" subj=system_u:system_r:prelink_cron_system_t:s0-s0:c0.c1023 key=(null)
Imho Selinux rule should be set even if its more or less a problem of os packaging.