The stage icons follow the texture setup below...
MenSelmapIcon.## - 64x56 pixels - CI8 texture / RGB5A3 palette
For the stage preview...
MenSelmapPrevbase.## - 176x176 pixels - CMPR texture
And if you're editing the contents inside MenuRule.pac...
MenSelmapIcon.## - 64x56 pixels - CI8 texture / RGB5A3 palette
MenStageSwitch.## - 128x64 pixels - CMPR texture
I guess I did it right because I saved the icons and previews exactly as you said and I tried it out in-game last night and they appeared beautifully. Only problem is the icons are a
tiny bit bigger than the normal stage icons, which is weird because these custom icons are 64x56... But it's not really noticeable anyway and they look like they were made in the game.
What exactly is "MenStageSwitch" for, though? And I don't believe I have a MenuRule.pac, either.