I have been teaching philosophy for a year now, and the Paradox of the Stone has

Read another response by Allen Stairs
Read another response about Logic, Religion
I have been teaching philosophy for a year now, and the Paradox of the Stone has come up again and again, boggling my student and me later on. The standard answer is that God cannot create the stone since it would imply a contradiction, and these philosophers say that even God cannot do that. But if He is God, why can He not create a contradiction? Is there something wrong with accepting the conclusion that God can make 2+ 2 = 5, given that God is all-powerful? Or put it another way, why cannot the concept of omnipotence be the ability to do everything, even if that would imply a contradiction?