I'm not saying it is unproblematic. I brought up Locke, not to advocate his theory, but to point out that Cael and Marx's argument is based on a false premise; namely, that natural rights land theory is based solely on conquest.The labour mixing metaphor is not unproblematic. I think it was Nozick (not exactly a skeptic when it comes to private property rights) who came up with the tomato soup example (if I pour my can of tomato soup into the ocean, do I lose the soup or gain an ocean?).
There's also the matter of the so-called 'Lockean proviso', whereby you must leave 'as much and as good' for everyone else. Locke was writing at a time where if you didn't have any land, you were more or less free to go out and claim some. It's more problematic now that every territory is claimed by someone or something.