Well, depending on what version of an OS X restore cd/dvd you might have, I was going to suggest as a last resort the Archive and Re-Install feature. This usually ends up being the end-all cure-all from apple support. The nice thing is that it saves all of your preferences and settings before re-installing the system.

I hope you get it resolved!

Also, have you tried re-naming the files before trying to remove them?

- trs