I am assuming by the way you've phrased your question that the game runs OK otherwise, and the only problem is with downloaded scenarios(?).
Does this include the Time Threat Paradox scenario?
civilization.gamestats.com/cgi-bin/civ2files/file.pl?id=336 - 11MB
Have you installed the patch?
civilization.gamestats.com/cgi-bin/civ2files/file.pl?id=334 - 3MB
Are you running other memory-hungry applications / programs in the background?
Have you attempted to alter any files in the game's directory?
When downloading the files, were there any interruptions during the download (e.g. modem dropped out)?