Thanks for all the help guys.
I bought Frozen Throne yesterday on my way back home from work. As soon as I got home, I went straight into my closet and took out an old shoebox that I've stashed some CD jewel cases in. Amazingly, one of the first cases I found was for Warcraft III! So I uninstalled the game, reinstalled with my original CD key, and then installed Frozen Throne.
It works perfectly.
Thanks again, reps have been issued.