If you want to change the overhead sprites you'll have to do it for every location.  Sprite tilesets appear across the entire ROM, so you'd probably have to search for their tiles' byte sequences to make sure you've found every instance in the file. 
Avatars, enemies, and spells are all coded similarly.  Their tilesets are preceded by data chunks that contain layout maps of tile reference numbers and what I suspect are palette references.  Each object has a local tileset that starts with a local index of 0x00.  Avatars have 4x4 maps.  Spells have three 4x4 contiguous maps to account for their 3-frame animations. 

Please excuse if I'm about to explain things that you already know.

If you have to insert an object larger than the original, then you will need to know how to correct the pointers to all its consecutive objects.  The pointer arrays are almost always at the top of the bank page (a multiple of 0x8000 + 0x10).  These are 2-byte big-endian and point to their corresponding addresses as they appear in the FCEUX hex editor.  $8000-$FFFF is the currently loaded bank of the ROM, so these pointer values will always be above $8000 (The game bank switches by writing the bank# to $5000.  e.g. Soldier tiles are stored at 0x1A00B2, 0x1A0000 = 0x8000*0x34, so it's in bank 0x34).  0x1A0020 is loaded to $8010, and is a pointer to $806B, which is 0x1A007B in the ROM.  The tileset starts at $80A2, so graphic object header is 0x37 (55) bytes.  Notice the 4x6 pattern grid starting at 0x1A0082 (actually I don't understand every byte in there yet).  Since this is the first enemy in the game, play around with 0x1A007B-0x1A00B1 (header) and 0x1A00B2-1A0221 (tiles)  to learn to manipulate its appearance.  Palette references are around the end of the header.  They let you change palettes of 16x16 blocks of the sprite.

Understand all the above and you're pretty much set to figure out the rest.

I'm on my wii right now so I can't post them, but I have some mugshots you could use if you wanted

Dr Mario sent them to me once. Unless he has new ones, they're:

Here's something that should help guide you with all the other avatars:
http://www.mediafire.com/?v4ecnng1dzy


I've noticed that enemies have 2 4-byte palettes stored right inside the header, using the standard NES color values.  They start with 0x0F (as the black color).  There are some bytes before the palettes that affect the way the palettes are deployed to the tiles, but I didn't find a pattern.

Let me know if you need savestates.

Now get started on the maps.

Will the patch go onto the original ROM or the translation?  If for the translation you'll have to specify upon release which version of the translation it patches to.  I'm going to replace some mugshots with better SRW mugshots by the time I'm through.  At this pace it looks like v1.00 may be ready for unveiling in just a couple of weeks.  It probably makes little difference as long as IPS overwrites instead of XOR's the data.

@Lindblum: I think I should make this for your translation and I was going to wait for v1.0 to be released at least before inserting any graphics. ^_^

@Darkdata: Thanks for that. And please, if you find any more data that could be helpful to this project feel free to post it! ^_^

My attempt at it:



Some notes:
It seems like each area uses it's own palette too. The Palette is repeated 3 times thought the rom. (Well, that area's palette).
For added fun, the textbox tile palette is shared with the roof tiles palette (hence the reason it's only simple)
I can't seem to find the tile assembly (meta-tiles) searches for them with wxyz, and wyxz orders do not find them. Could they be compressed?
I tried to copy Dr. Mario's style, unfortunately I still have quite a bit to learn.