Pues no he experimentado mucho con gba :v
pero eso es simplemente una de las limitaciones, el que hay pocas paletas disponibles y algunos sprites comparten la misma paleta asi que lo ideal es el lograr varios sprites usando la misma paleta.
Aunque si quieres agregar cuanta paleta quieras puedes...