What make of laptop?
Even with an OEM CD, it should be possible to start the recovery console, simple place it in the tray, and press Ctrl-ALt_Del (or power off/on) and wait for the recovery option to be displayed (from memory, this takes several minutes).
Firstly, try deleting the macromedia key (using reg.exe) but if that doesn't work and a repair install doesn't work, you'll have to go with a full clean install. If the CD is faulty (that is possible) you should be able to use another CD with the key supplied with the new laptop (in this case, activation may have to be performed manually, but this is not a problem).
From my own experience, a full clean install is a good idea with any new computer simply to avoid the garbage that comes preinstalled (for example, my Dell laptop under Vista took about 30 seconds to enter standy when I got it, but after a clean install it only takes about 3 seconds).