Винчестер проверить, конечно, не помешает. Для начала надо посмотреть информацию S.M.A.R.T. В «Винде» можно было бы поставить для этого бесплатную программку CrystalDiskInfo (crystalmark.info/software/CrystalDiskInfo/index-e.html). Но, поскольку Windows у вас пока нет, придется воспользоваться «линуксовым» пакетом smartmontools: загрузите Ubuntu, зайдите в интернет (надеюсь, сетевое соединение вы настроили?) и выполните в терминале команду sudo apt-get install smartmontools, а после нее – sudo smartctl -a /dev/sda (если речь идет о диске, который подключен к первому SATA-каналу).
Появится текстовая таблица, в которой надо обратить внимание на параметры Raw_Read_Error_Rate и Reallocated_Sector_Ct: если они приближаются к значению, указанному в колонке THRESH, винт действительно начинает сыпаться. Можно пойти еще дальше и прогнать тест MHDD (mhdd.ru/download.shtml), но, полагаю, это все-таки будет лишним, поскольку дело, скорее всего, вовсе не в накопителе. Ваш случай описан в статье техподдержки Microsoft support.microsoft.com/kb/314503. Вероятно, Windows не нравится «чужой» загрузчик в MBR.
Чтобы исправить ситуацию, сделайте загрузочный CD с DOS (образы можно скачать отсюда: www.allbootdisks.com), в CMOS Setup выберите режим совместимости с IDE контроллера ATA (в некоторых BIOS этот параметр отсутствует), загрузитесь в «чистый» DOS и выполните команду fdisk /mbr, после чего попробуйте снова инсталлировать Windows. Если это не поможет, при установке удалите логический раздел, в котором раньше была «Винда», и создайте его снова – должно сработать.
Теперь, по сути, осталось только восстановить загрузчик GRUB, но, поскольку вы уже «почитали доки» и даже все самостоятельно настроили, с этим, полагаю, тоже легко справитесь.