Starting a "Play Now!" game to clear hidden options (caused by moving from one mod to another) is a valid technique. I don't think that hidden options are responsible for this problem, however. When Farsight clicks on "End of Winter" his leader changes from his selection to "random", without changing his civ selection. This is exactly what happens when the "unrestricted leaders" option is selected, which is symptomatic of a bug that existed where selecting one game option had the effect of a different one, caused by reordering the options in the list without making some other necessary matching change elsewhere (if I understand correctly).
Still, there's no harm in using that technique to clear the options list, just in case there is some hidden option selected. Anyone who uses more than one mod should probably do it when they switch from one to another, just to be sure.
-------------
Farsight, the version you gave is the version of Civ4 you are playing (v3.19). To find the version of FfH2, you need to open the file "[path to Civ4]\Beyond the Sword\Mods\Fall from Heaven 2\Readme 041.rtf". The second line of text should give the version. If you aren't using version 0.41m then you may want to upgrade to the latest version and try again. I don't recall exactly which patch finally corrected this problem, so the latest version is my suggested fix. (The patch log implies that it was fixed with 0.41b, but since that is the earliest version that worked with 3.19, and you have 3.19 but also the problem, I suspect that the problem may not have been fully fixed until a later patch.) I am using 0.41m, and when I do what you did (single player >> custom scenario >> select a map >> select a leader >> select End of Winter) my leader selection does not change to "random" - so I believe that upgrading to Patch M will solve your problem.
