Por lo que veo el sprite está bien insertado. Obviamente el problema es la asignación o sustitución de paleta.
Pásame el ROM y el sprite y te digo cual es el problema porque estoy seguro que el tutorial está bien, pues he cambiado todos los sprites con ese método (incluso añadiendo más de 16 colores por sprite) y no he tenido ningún problema