Can you change to IDE mode from AHCI? That is a common fix for your problem, even if you are set to legacy or compatibility mode. The BIOS on laptops and OEM PC can be limited, as well as their use of terminology and the exact implementation of "legacy". On the Firmware Update download page, check the Read Me file for more information and examples of problems like yours.
BTW, how long do you wait while the update tool is scanning? On my PC it took quite a while, several minutes at least, and it is a Core i7 system (if that makes any difference) so it's a rather new, up to date PC, and might take longer on older ones, but that is just a guess.