Slightly different issue for me as I had uchg flag set, but I had to remove it from both the file and the parent directory in order to delete the file. I then added the flag back on to the parent directory.