The Australian English version of the game uses a CD key, but the UK / North American versions do not. With those, the error message mentioning a CD key means that it found the install disk (CD 1) in an optical drive, rather than the play disk (CD 2).
If you are using the play CD, try different optical drives, if available.
Are you shutting down all non-essential programs (especially anti-virus) before trying to start the game?
If that doesn't help, there may be a conflict between the copy protection and some driver that is different than before the re-install. In the error message, click the 'Information' button, then when that finishes, click the 'View Report' button. Save the resulting text file somewhere, optionally zip it, and email it to Larian (support@larian.com) with a description of the problem. They can create a file the copy protection can use to check your system on startup, rather then the play CD.
