If you have in the past found Gentoo to be too difficult or intimidating in the install process, then 2006.0 which has just been released has a graphical installer - it might be a more comfortable and familiar environment if thats what you are used to.
As for your laptop Induane, do you have any idea of the bits that Ubuntu cant work with, is there a new piece of hardware that is yet to be supported, etc? Theres a whole bunch of LiveCDs around that are fairly diligent and aggressive in probing for hardware and figuring out the right drivers, kernel modules, etc to use, if you are stuck for ideas try out the latest SLAX or Knoppix, see how well everything works, and get a list of all the kernel modules they load, output of \'lspci\', \'dmesg\', etc.
Laptops usually have odd video cards compared to desktop systems, if I had to hazard a guess as to how to get Linux working I would suggest using the latest driver package from ATI and see if that makes a difference.