Game won't start. Reports luaide.dll missing

[Dimension]

I just updated my GPU.Got a GTS 250 to replace my old 8800 320 MB.
Thought I would play some King's Bounty again, but the game won't even start up. I get a flash of the game icon at the task bar, and the DVD drive will spin for a while and then calm down.

I then tried to start the game from the bin folder in the CD and it told me it couldn't find luaide.dll, but I can find it in the Nobilis King's Bounty folder.
I've reinstalled the game twice, I've granted the computer full acess to the Nobilis folder (thinking that Vista may suddenly be blocking it), I run the program as administrator, I've tried shutting off my anti-virus etc.

Is the luaide.dll file only supposed to be in the King's Bounty folder and nowhere else.
I just can't understand why a file is suddenly not recognized after changing a graphics card.
All other games start up fine.

At least I've played King's Bounty to death before. It's fortunately not a new game, but I still would like to play it every once in a while. Hope someone is able to help.