yeah those icons are stored in separate places. as you know, the ones for the stage select are in sc_selmap_en -> MiscData[80] -> Textures, but the ones for the random stage switch are also located in common5 in sc_selcharacter2_en -> MenuRule_en -> ModelData[0] -> Textures. it looks like the ones for the main menu music selection screen are in mu_menumain_en.pac (in the menu2 folder), under MiscData[0] -> Textures.
edit: i will say that i had problems with file sizes being too big when i replaced both stage select icons and random select icons but a lot of that was probably my own fault with how i imported stuff. so be wary i guess