Thats wrong, they should have given you at least a bootdisc even if it is saved on the hard drive...Thats mad that, especially since they are if hard drives collapse, on another partition or not.
Seems like something more has happened in that case to that bit of the drive with the info on.
The best thing you could do is ring where you got it from and request for a boot disc to do this manually.
Though, you could try booting into Windows, does that extra partition show with the bootdisc info on it? You might be able to somehow run it from here and it might ask to restart (I don't know how those things work) or you might be able to copy this onto a disc if it has boot information on it... Though I would say your problem and ask for a disc.
Hope this helps