So the error you are getting is when the user checks/unchecks the box, is that right? I assume that the code to toggle the "lock" on the cell.
Try doing this:
ActiveSheet.Unprotect
'your regular code goes here
ActiveSheet.Protect
The other way to do this would be to put a Workbook_Open procedure in, which loops through each require sheet, and runs something like this:
ActiveSheet.Protect userinterfaceonly:=True
This would stop users from hitting your sheets, but let's macros do their thing. The only problem (and reason for the workbook_open routine) is that this setting disappears when you close the workbook.
HTH,