From FBSD_tips

The first time you see this message as root it can be disconcerting.

# rm -rf template
rm: template/bin/rcp: Operation not permitted
rm: template/bin: Directory not empty

Hmm, but I am root! Ah, yes, but files have more than just owner/group/world permissions, they have FLAGS! Man chflags. We'll list the flags with 'ls -lo' (o being the operative flag).

# ls -lo template/bin/rcp
-r-sr-xr-x  1 root  wheel  schg 18332 Oct  4 21:39 template/bin/rcp

And so, the solution :

# chflags noschg template/bin/rcp
#ls -lo template/bin/rcp
-r-sr-xr-x  1 root  wheel  - 18332 Oct  4 21:39 template/bin/rcp
rm template/bin/rcp
# ls -lo template/bin/rcp
ls: template/bin/rcp: No such file or directory

And if you wanted to do away with a whole directory structure, you could do this.

# find template/ -exec chflags noschg {} \;
# rm -rf template

Or

# chflags -R noschg

[edit] Discussion

Note that the ability to change certain flags is dependent on the current kernel securelevel setting. See security(7) for more information on this setting.

If your securelevel is 1 or higher, you will need to boot to single user to remove flags. If you set kern.securelevel to 0 in sysctl.conf, init will raise it to 1 when going multiuser. Securelevel can not be lowered on a running system.