Precisamente, debes usar otra paleta.
Por cada una de ellas puedes tener 16 colores distintos (15 + transparente). Y puedes colocar en el tileset todos los tiles que usen esas paletas.
Si quieres algunos con otros colores, pues toca usar otra paleta.
Respecto a la cantidad de gráficos distintos...