I finally figured out how to change Iceweasel's icon (which didn't change when I changed my icon theme). It's really quite simple:
1) Open up a terminal
2) Change directory to the one containing the icons: cd /usr/share/iceweasel/chrome/icons/default
3) Back up the old icons in case something goes wrong or you want your default icons back: sudo mv default16.png default16.png.bak
sudo mv default32.png default32.png.bak
sudo mv default48.png default48.png.bak
4) Link default48.png to the icon of your choice: ln -s /path/to/new/icon default48.png
That's it! Simply restart Iceweasel to make it use the new icon!