En que formato está el archivo?

Mod: tema movido

En caso de que realmente sea un archivo comprimido, entonces debes modificar el icono por defecto de la asociación del archivo, mediante el registro de Windows.

En caso de que sea un archivo executable (archivo con extensión .exe) entonces deberías poder modificar el icono en la tabla de recursos del archivo, mediante un editor de recursos.

Comienza por especificar la extensión/formato del archivo, no se que tipo de ayuda esperas si no das información útil para ofrecerte una solución óptima.
EDITO: Ok, ya lo hiciste.

EDITO 2:
yo puedo modificar perfectamente el icono del exe ePSXe, ¿qué problema encuentras?, explícate.

De todas formas ResHacker es muy tedioso, te sugiero utilizar la aplicación Restorator 2007, Anolis Resourcer, o PE Explorer Resource Tuner. (el más sencillo que te resultará es Restorator 2007)

Te indico los pasos usando Restorator 2007:
1. Cargas el exe al programa.
2. Vas a la carpeta "Icon", allí encontrarás el icono, con la Id 201.
3. En el árbol (TreeView) de carpetas y recursos que aparece a la izquierda, arrastras el icono que quieras desde el explorer hasta al icono de archivo con nombre "201", o directamente haces click derecho en ese icono de archivo que pone "201" y le das a "Assign" -> "Assign to..." para reemplazarlo por otro icono.
4. Apretas el botón de guardar, listo.

Saludos!

Para otra ocasión si los editores de recursos como el resource tuner, resource hacker, etc no te sirven lo que puedes hacer es usar el programa llamado File inspector para averiguar con que compresor esta comprimido el exe. Después ya solo sería buscar ese descompresor para descomprimir el exe, para por ultimo ya poder usar los editores de recursos antes mencionados sin problemas.

Lo malo es que los descompresores no es muy habitual que estén disponibles para la descarga pues suelen ser propietarios. Pero por suerte en muchos casos el compresor usado es el UPX que es un compresor libre que es bien fácil de encontrar en la red.
Saludos...

Songoku