A mí me funciona bien. Creo que tu error puede estar en que la imagen que me has pasado es un .bmp y no .png y a lo mejor estabas escribiendo mal la ruta, nombre y extensión de la imagen dentro del código (a lo mejor estabas poniendo ...\...
Nueva imagen.png).
La imagen no ha de ser PNG a la fuerza, puede ser BMP, JPG... pero tienes que tener cuidado a la hora escribir bien el nombre y la extensión en el código.
Te dejo el código y una captura. Simplemente ajusta la ruta para que señale a donde tienes tú guardada la imagen (en mi caso estaba en el escritorio):
<ScreenOverlay> <name>Legend: mi leyenda</name>
<Icon>
<href>
D:\Users\Fran\Desktop\Nueva imagen.bmp</href>
</Icon>
<overlayXY x="0" y="0" xunits="fraction" yunits="fraction"/>
<screenXY x="25" y="95" xunits="pixels" yunits="pixels"/>
<rotationXY x="0.5" y="0.5" xunits="fraction" yunits="fraction"/>
<size x="0" y="0" xunits="pixels" yunits="pixels"/>
</ScreenOverlay>
CULEBRAS GIS