I think you're stuck with this protection problem. You'll have to unprotect / protect the worksheet when running the update to get it to work.
If you're worried about leaving the sheet unprotected on unexpected program termination there are a couple of things you can do reduce the likelihood of leaving the sheet unprotected.
1) You can cut out user interferance by using Application.XlEnableCancelKey = xlDisabled (or xlErrorHandler). This will stop the user being able to interupt program flow with Ctrl + Break.
2) Introduce an error handling section such that on any error the program flow is directed to a closing clean-up section that will include the re-protection of the required sheets.
Code:
Sub Test()
On Error GoTo ErrHandler
' Main program
Exit Sub
ErrHandler:
MsgBox ("Error Occurred!")
ActiveSheet.Protect
' Other clean up
End Sub
Maccas