Given that there are many sizes and color depths for different phones (even for the same manufacturer), i would like to have one application for all of them and then, download a proper icon for the phone de app is downloaded into.
Is there a way to change the MIDLet icon once the application is downloaded?
As far as I know there is no way of doing this. You can however force the user to upgrade an app and change the icon then. This can be done in a more user friendly manner without loss of content downloaded by app.
Although there is no way to do this in standard j2me (except upgrading, as omermuhammed wrote), if you are targetting handsets that allow native development (Symbian phones come to mind) you may be able to either register a different file as the MIDlet icon or overwrite the existing file (by running native code, not java) after the MIDlet has been installed.
Some newer Sony-Ericsson phones (with the JP8.3 platform onward) have a proprietary java application management API that can only be accessed if your MIDlet is signed by Sony-Ericsson, along with jad properties that allow you to hide your MIDlet icon from the user. Although I don't think that really allows you to change the icon, it can facilitate auto-upgrading.