j'ai eu pdt lgtps ce probleme aussi, uniquement avec debian (et non avec mandrake ni FC). J'ai essayé de passer le PS/2 en module, etc, rien n'y faisait, j'avais toujours le clavier et la souris qui ne s'initialisaient qu'une fois sur trois ou quatre.
Un jour j'ai nettoyé mon GRUB, retiré un bon nombre d'entrées qui n'etaient plus utiles, et depui je n'ai plus jamais eu aucun probleme a ce niveau là (ss meme changer de noyau).
Je ne sais pas si c'est vraiment lié ou pas, si c'est que GRUB pose probleme (je n'avais jamais ce soucis avec LILO, meme avec debian).
A essayer en tout cas ...