I've written an app that does something along those lines of what you're trying to do, but it's not in GBA format.

 Can you post a pic of the original and your new version with the correct colors(outside the emulator)?

This isn't exactly what I do, but what I'd do if I were you would be to use two copies of yy-chr. One of them has the rom, the other is a blank file which I use as a buffer.

Make sure both programs have the same palette loaded, then I import a BMP file into the window with a blank file. After that, I just select, copy, and paste from one window to the next. Since it's the same program, there's no clipboard issues at all. Simple, but functional!

After that I just hex edit the file to make sure the tilemap is correct.

KaioShin: I'm making some assumptions. The tiles are 4bit 8x8, there is only on BG plane, no sprites, only two 16 color palettes are used, and the pics you posted aren't shifted n number of pixel for X/Y? Is it possible you can post the palette data from those two palettes entries, exactly as they are(color order) in the game palette index? The tile map data would be helpful, too.

 I ran the original through my app and it created 3 (16,16,14,14) color palettes and your new one with 3 palettes (16,14,14). If I had the additional info, I could probably fit it back into the two palettes by hand.

I took a look at the savestate and reconstructed the BG0 plane from the tiles.



Since I don't have the tilemap info or the palette info, you can see where the tiles from different palettes based on the "hard" edge against their neighbors, when the whole tileset it set to a fixed 16 color palette. Comparing this against the original snap shot(which is aligned correctly - thankfully), you can isolate those groups of tiles. Here's a breakdown.

Palette set 1: 16 colors


Palette set 2: 14 colors


Palette set 2: 15 colors


Palette set 4: 14 colors


 About 3 or 4 of the main tent tiles could be using part of the text+tent palette colors, but it's probably unlikey since you need a whole 'nother palette to represent most of the other tent tiles colors.

 Since you have access to the tilemap from the rom, you'll need to make the right correction for the right new tile changes. The upper part of the tent shouldn't need tile or pal index replacement, and the new lower part should use the same palette indexes as the above tiles, etc. You should probably dump the palette data so you know what order the pixels in the tiles belong in/reference to.

I think you can do it with Bimbo, a program used mainly for GBA splashscreen images.

http://www.pocketnes.org/tools/bimbo1_3.zip

I had the same problem when I tried to insert the titlescreen I made for Summoners Lineage, but I didn't know any tool that would help me so I had to do it the hard way. If you can't find a tool to help you try this:

1.Extract the titlescreen tilemap (I used unLZ-GBA).
2.Choose any color from the image you extracted and then paint the image with that color.
3.Reinsert it and run the rom, now you will be able to see the palletes that the tiles are using.
3.5 Replace the titlescreen with yours and extract it.
4.Open photoshop and make a 8x8 grid (theres an option somewhere).
5.Create 3 layers (one for the titlescreen tilemap and one for each pallete).
6.In the first layer the tilemap is probably scrambled so you will need to reorganize it.
7.Copy it to the other 2 layers.
8.Now erase the tiles that don't use their respective palletes.
9.Create two rows of 16 squares in each of the palletes layers.
10.In the first row use the color from the tilemap and in the second use the equivalent colors from the screenshot.
11.Use the magic wand to select the color you want to replace always using the pallete from the tilemap.

I Really, really, really suck when I try to explain things in english, and this was the way a noob did.
I was trying to help but I don't think you will understand ( my fault) you will probably discover a much better way to do it

I'm really looking forward to this translation uou're doing a great job.

EDIT: Tauwasser Posted faster.

I've always had trouble converting images to game data, save NES, and that was after recoloring the image to the converter's palette thing >.>"";;

For GBA, the best thing I found was usenti.  But it had the same problems as all the other programs I tried:  let's say there was 16 color.  After converting the image to data, I'd open the tile with YY-CHR, and now the image has 13 colors, 8 colors, 4 colors, some weird thing like that, and I'd always lose quality.  The best way I got around it was manually recoloring the 16 colors different ones, so that each color was exactly distinct in color, and even then, Blues would become Reds.

It's that kinda stuff which got me to stop one of my favorite projects, as inserting over a hundred of these:

had to either be fully by hand, pixel-by-pixel, or after being converted and still having to be gone through by hand shadding in the colors which didn't show up.