Heres what I did:
1. Goto unlz-gba with your rom. Tick 256 colours and BlackWhite.
2. The hero image should be around 341. Once you find it, click the + and - signs until it looks correct. Save it.
3. Load your rom in VBA. When you see the Intro hero sprite there, goto Tools->Palette Viewer and select Save BG. Save it as a .ACT file.
4. Open the image you got from unlz-gba in Photoshop. Goto Image->Modes->Color Table. Click on Load. Load the palette from VBA.
5. After the palette is loaded, check the first colour in your intro sprite and change the first colour in the palette to match that colour.
6. Now save and open that image in Paint.
7. Paste your hero sprite on that image. It will have a few colour changes but it won't matter much.
8. Now in unlz-gba, goto the number of the hero intro image, and check 256 colours. Import the image. Write it to rom.
Now the intro sprite should be replaced correctly. By this method, you don't even need to change the palette in the rom. You can repeat these steps for Heroine,Professor and Rival also. If you are still having problems, feel free to tell me.