puedes usar las funciones BeginUpdateResource(), etc. puedes encontrar info en msdn. Yo intenté hacerlo en C y lo más que logré fue cargarme todos los iconos del .exe 

Mira, la verdad que el código es algo complicado a primera vista para intentar ver dónde puede estar el problema.. pero bueno he probado el programa y...
A mí no me da ninguna clase de error..

Es decir, he cogido un ejecutable que tenía un .ico de 32x32 a 256 colores.
-Se lo he cambiado por otro de 32x32 a 256 colores y sin problema.
-Se lo he cambiado por otro de 16x16 a 256 colores y sin problema.
-Se lo he cambiado por otro de 32x32 a 16 colores y sin problema.
-Se lo he cambiado por otro de 16x16 monocromo y tampoco me ha dado problemas..

Después he cambiado el icono original de 32x32 y le he puesto uno de 16x16 a 256 y he hecho un montón de cambios también y no me ha dado ningún problema..

Tal vez esté equivocado pero se trata de cambiar el icono del ejecutable no?? (esque da ambigüedad eso que dices de editar el icono ...)

PD. Lo que sí he comprobado por ej. es que si un programa como suele ser normal tiene varios iconos, se pierden todos y los modifica por el del ejecutable..

Perfecto!! ya he encontrado la solucion!!

El problema no estaba en la función si no en el archivo .ico xD Estaba metiendo un archivo ico que solo tenia una imagen de 32x32, por eso no se veia la del 16x16!!

Que verguenza, jojojoj vaya fallo he tenido xD