do you changed your startrom.0 file?
s. the following docs:
a newer bootmenu.1/dosundi.1: (solved my Lenovo trouble in the past)
Did you update you BIOS? I've had some troubles in the past with an xw9440, it's fixed after BIOS update...
Another workaround I found (with DOS) was to attach a external (Dell) USB floppy on a Lenovo notebook...
I tried everything you suggested and it turned out to be the BIOS that needed updating.