To add a bit in the same vein as [Jake's answer](http://judaism.stackexchange.com/a/16315/1442):

This is not a real paradox; it is simply a matter of definitions. "He who can make five into ten without adding to it" is a great example of this; making five into ten entails adding by definition. 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.