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.