I totally figured out how to fix this problem!!!
Ok... here it goes...
When you go to install the new disc, the default file path it goes to is different than the original CD... Therefore when it tells you that you are unistalling the old one... you really arent.
You need to go into the control panel and delete it off of the programs listing.
Then...you need to go to program files in the C drive.
There are two folders with the game in it.
One is called 2K games and the other one is called firaxis. THIS IS THE PROBLEM!
You need to COMPLETELY rid your computer of the ENTIRE game, in EVERY folder.
So... after you have uninstalled in the control panel...look for these folders and delete the ENTIRE folder.
After you have done that, go to the search box on the start menu and type in civilization and see if anything else is left on your computer (there was one file left on mine when I did this.)
After you have COMPLETELY REMOVED every part of this game from the computer...
RESTART.... REINSTALL.
Does that make sense? hahaha. I did this and it worked on my computer. Let me know if you have any questions.
WHOO HOOOOOO!!!!!!
PS... After you are done reinstalling... it will STILL not give you desktop icons... you will have to go into the games window of your computer and physically put one there yourself... also... my computer automatically opened up colonization again... I just exited that game and clicked on the other one.