Apple - File can't be moved by root on OS X

For people stumbling upon this in an OS X 10.11+ era (El Capitan or newer): Apple has added a whole new layer of security in OS X. They have taken away some privileges from root. The file you are trying to modify has a restricted flag. Only restricted processes which are signed by Apple will be able to modify these files. However, you can disable this security system by booting in recovery mode and disabling it in a Terminal by doing: csrutil disable.

Alternatively, you can also just start Terminal in Recovery Mode and delete the file there. Or even try booting in a Linux environment with HFS+ support (at least if you're not on APFS yet) to change the file.

Sounds like the file is locked to me, which is why the uchg attribute is appearing. You should be able to use the following command to remove the locked attribute:

chflags nouchg file

or right-click the file in the Finder, click "Get Info" then uncheck the "Locked" checkbox

Try:

chflags -f -R nouchg directory

on a higher level directory to stop this problem.