If you searched Google, you’d find that messed up app icons is a common problem of iPhone’s 3.0 firmware.
Until Apple releases a fix (possibly in firmware 3.1?), there is a quick and easy fix. Everything is done on your iPhone, you don’t need access to your iTunes library.
1) Remove an app that has incorrect icon (preferably one that has no data stored on your iPhone, so you don’t have to worry about losing data).
2) Download and install the app again from App Store.
3) As the application is being installed, hold the power button and turn off your iPhone!
4) Turn your iPhone back on. You would now notice that all application icons are back to normal. The application you were installing is installed as well.
Hope this tip benefits some people. :)