Solo puedes cambiarle el icono a los accesos directos y a las carpetas.
Si lo que quieres es cambiarle el icono a un acceso directo realiza lo siguiente:
1. Clic derecho sobre el icono.
2. Selecciona propiedades.
3. Selecciona la pestaña programa
4. Haz clic en cambiar icono.
Windows tiene lo que se llama caché de íconos. A veces, este !"·% caché se "rompe" por algún motivo incomprensible. Tendrías que bajarte un programita para recrear el caché, como el ActivIcons.