Because Allah can do what he wants. So if Allah decides this rock cannot be lifted by Allah, so it is.
Note that there is nothing stopping him from deciding later than he, in fact, can lift the rock. Why? Because Allah can do what he wants. So it's like Allah playing mind-games with himself.
This is a game of logic where a player can alter the rules. There is no contradiction in the question, at least none that I can see.
Now let’s assume he can't change the rock's properties once created (which in turn re-iterates the question, but let's pretend). Can Allah move an "immovable object", without giving himself the power to do so? The answer is yes again.
To move something is to alter its distance from something else, i.e. a point of reference. For Allah to move the rock, he must move everything else. The rock's true point of reference is the same, the Universe's point of reference is not.
It's the same as drawing a dot on a piece of paper on your desk, and wanting to move the dot further from your lamp. You can't move the dot, so you move the paper.
You might say that's not a good answer because the rock is still in the same place relative to its true point of reference, no matter what happens to the universe around it. And suddenly we aren't dealing with the omnipotence paradox, but with this question:
What happens when an unstoppable force meets an immovable object?
Which is a different paradox altogether, and is nicely explained in this video by MinutePhysics.
Evpok suggests that answers should come from an Islam-theistic point of view. This is very difficult as yours is a logical question requiring a logical answer in a theistic setting. The two don't really play well together.