The easiest thing to do is to download ibrickr 8.0 and then go to files, applications, then if i can remember correctly a long list of names for the programs on the springboard. Look for the icon you want to change (it will end in an .png). Take the new picture name it exact same name and upload it into the iPhone. I would recommend hitting the download button first so you can download the original picture just in case you don't like the new one, you can place the old icon back in.
Yeah what is with that stupid green mushroom? It's the wrong shape and it doesn't show off the fact that you have Nintendo without pushing it. And every time I update I have to change the icon again, pretty annoying.