GNU Icecat was GNU Iceweasel, but the reason they changed the name was because Debian also used "Iceweasel" to rebrand their slightly tweaked version of firefox. What the "tweak" amounts to may just be the logo; since it involved a license Debian considers "non-free", they wanted a firefox they could distribute without it, which required a rename.
A bit odd, but I presume that Debian, GNU, and Mozilla have a mostly friendly relationship. Somewhere I while back I saw a GNU comment regarding "Why Icecat?" to which the answer was, "Because it's not Firefox", but clearly "Iceweasel" was a better inversion, and it sounds to me like this was used first to refer to any pseudo-firefox, which explains the eventual GNU/Debian confusion.
So, currently: Icecat is a repackaging (and modification) of firefox by GNU. Iceweasel is a repackaging (and modification) by debian. The Icecat wikipedia page states that "The GNU Project keeps IceCat in synchronization with upstream development of Firefox", so I would presume their version numbers match up. It looks like Iceweasel does almost the same thing, although it may skip more versions and be further behind at points in keeping with general debian practices.