Это должно быть хорошим началом.
Я предполагаю, что вы не передаете chflags в mv, что не имеет смысла, а просто переименовываете файл, если chflags не удается. Обработка расширения более сложна, но, безусловно, выполнима.
find . -flags uchg -exec sh -c "chflags nouchg \$0 || mv \$0 \$0_LOCK" {} \;
Редактировать: переименовать, если chflags успешно :
find . -flags uchg -exec sh -c "chflags nouchg \$0 && mv \$0 \$0_LOCK" {} \;