Wasn't until a few days ago when I think I made some serious progress. Here's what I've got.
First of all, if you go to 0x5C001, you'll find three bytes. $97, which is the width of level in 32x32 blocks. $0C, which is the height of level in 32x32 blocks (+2). And finally $BF, which has something to do with the sprite array. More on that later.
After there bytes, the level data begins. It is compressed in a way that I have yet to FULLY document, but I've made some changes in the level already. Editing the first byte, for example, will change one of the cloud blocks to something else. I tried $00, $01, $02, $03, all the way to $7F, screenshotting my way to a full tileset rip. Observe:
Each level has only $7F blocks to choose from. If the tile to use goes above $7F, the level breaks, but only in the ROM. What I did next was compare the level data dumped to a KiGB (possibly every other GBA emulator too) save state, and found that one byte consists of STTT TTTT bits, where T means tile to use ($00-$7F) and S being the sprite flag. If the bit is set, a block is printed but with a sprite on top of it. So, for example, $2E is the rooftop block, but $AE is the rooftop block WITH a sprite on top of it.
This is the level data in the FRZ (0x2660, $716 bytes long) overlaid on top of Blaziken's fantastic rip of the map:
If you pay attention to the blocks with sprites, you'll get the idea behind the sprite flag bit.
So, a thing worth mentioning is that the whole level with sprites (and possibly even bonus levels) are loaded all at once, so in theory, it could be very possible to make a program that reads the Save state of the level as input and spits out a complete map of the level as PNG. Automated mapping in a way.
But in the end, I'm pretty confused. How does the game transfer the level data from the ROM into the complete block array seen in the save state? There are similarities, but I've never dealt with compression algorithms (except RLE) unless there's an automated tool to do it. Although I doubt it, it might be the same/similar compression as Donkey Kong Country 3. I know Kirby Super Star (SNES game) uses the same compression as Kirby's Dream Land 2 (Game Boy game) and Kirby's Adventure (NES game).
If anyone here has binary file comparison software, could he/she look into the compressed and uncompressed level files for analysis?
Here is the uncompressed file from the FRZ and here is the compressed file, from the ROM.