The description, categories, screenshots, etc. (i.e. meta-data) take a few hours to become effective.
The "real" icon (the 57x57 one and not the 512x512 one) change is another issue since the icon is embedded in your application file and I have no idea what happens. You basically have to re-submit your executable and I'm guessing that will involve a completely new review.