I've waited since the iOS 4 keynote for the new phone. It's kind of weird that my artwork on the iPod looks amazingly clear when those are only 600x600. The app icons are 500x500 and they look pixelated to hell. I'm confused.
Icons on the iPhone 4 are natively 114x114. When submitting an app built with iOS 4 developers must provide these hires icon in addition to the regular 57x57 icon. There's a little more to it than that too, as there are resolutions for Spotlight search results and the Settings page, but of course this in itself is no big deal.
Now of course scaling down your 512x512 icon (which you need for iTunes) to any resolution is easy, but people need to remember that a developer is likely to want to update more than just the icons - ie they ideally want to update the app to take advantage of retina display too.
This takes time as even though for 3D games it may merely a flag in your GL layer, there are performance ramifications with this, and the optimisations take time.
Higher model LoDs may be needed due to the higher res again affecting performance. Also, as already said 2D art may all need re-doing. None of this is trivial.
Remember too that even after an app has been updated and submitted it takes time to get into the store.
One theoretical possibility is when installing an app all the icons could be auto generated from iTunes' 512x512 icon (and devs only had to submit one icon), ie with iPhone 4 they could all automatically have been optimal resolution from day 1. The reason Apple doesn't do this is so devs have full control of every pixel at all resolutions.
