This message could occur during the boot process, making the time for it very long. Usually, messages such:

ata2: ... configured for MWDMA2...
....
ata2: link is too slow to respond
...
ata2: soft resetting link

might be seen during the boot or after (using dmesg).

HOW TO FIX

Idenfity which ata is involved using dmesg | grep ata. In our case it's ata2 (cdrom).
Then, pass libata.force=2:pio4 to the kernel parameters in your grub/lilo config (number 2 is the one from ata grep).

Next boot, this will force pio4 mode on cdrom without waiting for a search result.