I had the same problem, with external harddrive freezing the machine during boot up.
I also tried all the above fixes.
1-usb legacy - turned it on turned it off turned it to auto and nothing worked.
2-made sure the boot sequence was correct and that didn't work
3-diabled cd roms and floppy from boot sequence and that didn't work
4-used different keyboard and mouse and that didn't work
I went into device manage and updated the drivers for USB controller and voila now it boots properly. These drivers should have been updated automatically but they werent, don't know why but for me that was the problem.

Pip22 DOES have the CORRECT Solution! Go in the bios and "DISABLE" USB LEGACY SUPPORT. This does work every single time. Once you select "disable" then select f10 to save the new settings---but before you exit/restart, Plug in your external hardrive---then restart---problem solved!

"Find (in BIOS) the "USB Legacy Support", make sure it is set to "Enabled"

That's rather curious advice because the official fix from Seagate & Western Digital, (and the advice from most people who've fixed this problem) is to set "Legacy USB Support" to DISABLED. You're saying exactly the opposite!

Thank You Pip22-your solution was the ONLY solution that really works!

perhaps it could now be marked as solved!
M