I have to believe that this is really quite simple and straight forward.
Put a break point at the start of your code to address the first 2 quotes above. The next quote suggests that this is all happening in the sheet SelectionChange event
so I would put the break there. Select a cell in the same column and the code will halt at the breakpoint. F8 one line at a time and watch what is happening. Since you mentioned protection earlier, you must be trying to edit a cell somewhere after the sheet it protected (or when it still is protected if you're not actually cycling protection off/on) and that is what raises the error. Step through the code until you find out which line raises the error.
Only you can really say how to fix this. One way is to leave the protection off until the very last part of the SelectionChange event. Another method might be to test if protection is on for the cell you have a) selected, or b) are trying to change, then if it is, do not allow user to make a change or do not have your code make any change - whichever it is you are doing. Or unprotect and change (or don't protect until the end or exit of this sub as I've already stated.