En fin, lo siento también por no haber testado esto, pues no estoy en condiciones de lo hacer.

Si, en teoría es posible. Solo hay un pequeño problema que no te he hablado por no me haber recordado. No sé si conoces las áreas de memoria del GBA.
Esas son:
00000000-Bios (16kb)
02000000-EWRAM (256kb)
03000000-IWRAM (32kb)
04000000-I/O (Input/Output) (1kb)
05000000-Palette RAM (1 KB)(256 BG colors, 256 OBJ colors)
06000000-VideoRAM (96 KB)
07000000-OAM (object attribute memory) (1 KByte)
08000000-ROM (32Mb's MAX)
0E000000-Save RAM (32/64 Kb)

Como te he dicho en MSN, las 256 colores (excluido 8Bpp's) son posibles usando 16 palletas de 16 colores cada una (16*16=256).
Si, tengo cuasi la certeza que esto resulta pero, en teoria, al cargar 2 palletas, vas a sobrescribir la paleta 2 que ya estaba usada por otra cosa cualquier (toma de ejemplo las paletas del OverWorld, de los tilesets. Solo hay 12. Porque? Porque las otras 3 son para las cajas de mensaje y otras cosas), pues la area de palletes del GBA no "incrementa" solo por se cargar 2 paletas.

Así que este método debe ser utilizado con precaución, solo en situaciones especiales, como en portadas, que las paletas son utilizadas todas para la portada, o el WorldMap, y nunca cuando la paleta siguiente es utilizada por otras cosas.

Atención: Esto es todo teoría, entonces no sé si el metodo funciona.

Bueno, es solo para dejar ese aviso. ;)

Saludos de Sonicarvalho