I have fixed it. The problem lies with Civilization IV complete registry keys. Here is the "Civilization IV" registry key, with InstallDir;
Now if you look in the "Beyond the Sword" registry key folder;
You can see that the "complete" edition has no "InstallDir" registry key here. So I manually added one as per this screenshot;
And voila, History In The Making now works
Note: The full location of the registry key looks a bit odd because it's Vista 64. Users of Vista 32/Windows XP may need to look elsewhere for their civilization iv registry key, but the same principle of the fix applies to anybody that has the "Complete" DVD edition - just insert "InstallDir" in to the "Beyond the Sword" key folder with a complete path (including trailing "\" at the end) to the Beyond The Sword folder within the Civilization IV folder.
Hope this helps others, and maybe you can add this to the FAQ for now Grave?
Thanks both Dale & Grave for helping with this problem