I don't have a real solution, but I've experienced this too on my 3GS. I just bought a copy of Myst and put it on my iPhone, but the icon was of a dimmed AIM icon. A restart fixed it, but who knows what that was!
Try going into settings---general---restrictions---enable restrictions. Turn Installing Apps off and reboot. Then turn it back on and reboot. This fixed my missing icons so it may fix your mxed icons.
Try going into settings---general---restrictions---enable restrictions. Turn Installing Apps off and reboot. Then turn it back on and reboot. This fixed my missing icons so it may fix your mxed icons.