[Franz Härtl]

I know this is age old, and it’s more than pathetic that this is still an issue TEN FREAKING YEARS after the initial question was asked. I had exactly the same problem though: Illustrator CC trying to paste to seemingly random layers, even if they were locked. Even more weird, upon pasting AI inserted stuff from the pasted layer into seemingly random sublayers of the layer it insisted on pasting to. It drove me nuts, and I was about to reinstall as was suggested here.
I came across the “solution” (or rather the cause) of the problem recently. I post it here, because this thread is still one of the top results if you google the problem.

As often is the case with Adobe it is a well meant but horribly implemented feature, not a bug.
The problem arises when “preserve layer order upon pasting” is active (it is deactivated by default, which is probably why reinstalling appears to fix the issue). To really fix AI you have two options:
1. deactivate “preserve layers when pasting” in the layers context menue (the one in the top right corner of your layers-area). You then have to live with AI messing up your sublayers by moving everything to the top layer. In case you don’t use complex sublayer setups or get used to using groups instead this might be a simple solution.
2. make sure that the layer you try to paste (i.e. the source) has a different NAME than ANY of the layers in the file you try to paste to (i.e. the target). If you do that AI adds the pasted layer with preserved layer-order as a new layer.