To add a bit in the same vein as Jake's answerJake's answer:
This is not a real paradox; it is simply a matter of definitions. "He who can make five more than ten without adding to it" is a great example of this; making five more than ten requires adding by the very definition of the ordinal system. A rock is by definition material, and lifting is by definition an act applicable only to the material.
Since God is omnipotent, he can lift anything that is definitionally subject to lifting. Therefore, to put it clumsily, "God cannot create such a rock" because God would by definition have to make it something other than a rock in order for it to no longer be subject to lifting.