Hi, welcome
I haven't tried it again since I upgraded Parallels to version 4, but when I tried just now, it failed in the same way as yours did.
I tried a second time, double clicking the desktop icon for Colonization. When the error message came up again it said it had timed out waiting for the CD, and had a "Retry" option, which I clicked. While it was searching for the CD again, I right clicked the CD icon at bottom right of the VM window and selected "Configure ...". In the VM config screen that came up I just clicked OK. I think that caused the CD to remount, and then the game started up. I've repeated the error several times, and have found no tricks to ensure that it starts up reliably, Patience and persistence seem to be required
Disk-based copy protection systems seem to be a bit flakey. I've had similar problems with the Mac versions of Civ4, and repeated eject/reload/relaunch cycles have been my only way to solve them. I think there are some very tight timings involved in the checking software, and Parallels version 4 may have changed something and pushed it close to the edge for Colonization.
For reference, I am running Parallels build 4.0.3540 (November 22, 2008) in OS X 10.5.6. I normally start and run the VM in a window, though I can switch to Coherence mode to have just the game window displayed within OS X.