No estás haciendo el orden bien, me parece.

Lo que tienes que hacer primero es cargar la paleta en el A-map. Después, guardas el tileset, lo editas en paint y vuelves a cargar el tileset en el A-map. Guardas y todo listo ;D

El problema cuando lo haces como lo has hecho tú es que estás reemplazando los tiles en un tileset con unas paletas distintas, por lo que al cargar el tileset ya editado las paletas se descolocan otra vez y por tanto queda negro.

Dime si funciona, pero estoy seguro de que es por eso.