Isn't it likely that the issue is with the os? I wouldn't want to send off my computer to have a factory hdd image when I got it back
I thought you were experiencing this issue with the Lenovo factory image
In such a case your laptop would have been probably eligible for warranty service. (BTW, you don´t need to send the laptop for repair with the HD included.)
Anyway, yes, it could be a software issue, only that part with exiting from BIOS is somewhat dubious, because BIOS is actually independent from OS and if you don´t enter in BIOS, my understanding is your laptop boots normally in Vista. Actually, this issue could be also BIOS-related (to be honest this now seems very likely to me). What BIOS version do you have? There might be a BIOS update that applies here. I would also run PC-Doctor/Lenovo System Toolbox to exclude any hardware-related problems.