Tengo entendido que ese paint no maneja muy bien las imágenes indexadas, generalmente los tutoriales lo manejan con versiones mas antiguas, a mi me paso lo mismo cuando quería insertar tiles, por lo que recomiendo que en donde dice "pegar" des click en la flechita he indiques "pegar desde.." y selecciones tus tiles que quieras insertar.
A mi me funciono de esa manera, espero que te funcione a ti tambien.