Tim,
I am getting the same message when I try add fields to a FC within a personal mdb on our network drive. When I make a copy of the mdb and add the copied FC, I can do all the adding I want. I have about 10 .ldb files in various folders on our network. I have tried to delete them manually, but it says that it is being used in another application. A previous thread suggested going to Microsoft's web page and under sysintall download a free Process Explorer and that it would see what application was locking the files. For me, I wasn't able to see a program that was running any GIS applications, as I had shut them all down.
We don't run SDE as we are a small municipality, so our issue may not apply to you. When I talked with ESRI, I was told it was a problem within my antivirus software. That the antivirus software is what was keeping the locks in place. We needed to shut off our antivirus and then recheck the locks. Our IT said that was not the case and that this happened after we upgraded to 10.1. So, I am stuck in between the two immovable, infallible forces, IT and ESRI. Good luck. If I find a solution I will post it here.