This question hinges on the fuzzy and difficult distinction between logical contradiction and paradox.
A logical contradiction is a statement made from within a logical system that expresses antithetical propositions as simultaneously true: the classic 'p and not-p' condition. Within that logical system, a logical contradiction points to a failure of logic. Something, somewhere, has gone wrong, and we need to go back and hunt for bad premises or logical missteps.
A paradox has the same form as a logical contradiction — mutually exclusive propositions are expressed as true — but it is made from above a logical system. A paradox asserts that there is something about a logical system that we do not (yet) understand, and our lack of analytical understanding makes us perceive a contradiction that isn't real. Generally speaking (though perhaps not exclusively), paradoxes occur when something outside logic runs up against 'pure' logic: e.g., Zeno's observation that a runner can never 'logically' cross a finish line when runners 'physically' do that every day, or Russell's paradox pitting the logic of set-inclusion against the real-world (or at least mathematical) notion of a set.
So the issue boils down to this:
- We have a logical contradiction if God does not obey the laws of logic that he (ostensibly) created
- We have a paradox if we do not understand the laws of logic (ostensibly) created by God
If we make a statement like "An omnipotent being can/cannot create a stone s'he cannot lift" — and note the similarity to Russell's paradox, which asks whether the set of all sets that do not contain themselves does/doesn't contain itself: a problem of exclusionary inclusion — it may seem like a logical contradiction from our perspective, wrapped as we are in the limitations of human cognition. But from a perspective above our limited view, we may look as silly as a child insisting that a runner can never cross the finish line, because reaching the finish line is contradicted by logic.
How can we know whether we have established a firm contradiction or ensnared ourselves in a mere paradox? That's a far more difficult question than one might imagine.