A similar paradox is the question: what happens when an irresistible force meets an unmovable object? Here, irresistible means it can move anything, and unmovable means nothing can move it.
In both cases, the question is making implicit assertions that are inconsistent and self-contradictory. In the first paradox, the phrase omnipotent being is implicitly stating that any phrase such as a stone too heavy for him to lift is meaningless. In the second paradox, the phrase irresistible force is asserting that there are no unmovable objects for it to meet. The phrase unmovable object is asserting there are no irresistible forces for it to meet.
Thus, one solution to this type of paradox is to say that it is logically impossible for both objects to exist at the same time. So, there cannot be both an irresistible force and an unmovable object.
In the case of God, a similar response is available if it is already accepted that God cannot do what is logically impossible:
However, the answer above can be restated even if one does not already accept that God cannot do logically impossible things: one can answer that the question is literally meaningless, and therefore there is not even a logically impossible task being set.
This is a useful distinction if one wants to hold (as some, including Aquinas, have held), that God can do even some logically impossible things, such as making 2+2=4 false.
Another solution is simply that an omnipotent being can create a stone too heavy for him to lift. The being's omnipotence depends on the nonexistence of such a stone, but his omnipotence also implies that the being can give up his unlimited power if he wishes. If he were to create such a stone, then he would in effect be relinquishing his omnipotence, but no logical contradiction would arise.
See Omnipotence for a discussion on the various positions regarding the meaning of omnipotence.