if you right click on the shortcut you made and go to Properties
and click on the icon in the box that appears, you should then be able to change the icon.
Alternatively, both KDE and Gnome allow for most of the system icons to be changed by installing a new set.
Noia Warm for KDE and Tux n Tosh for Gnome are FINE examples of better replacement icons. (including a better Gaim icon.)
See
http://www/kde-look.org
and
http://www.art.gnome.org