While I don't have any personal experience with linux and laptops, I've read many reviews on the web regarding the ibm/lenovo line of Thinkpads as being about as rock solid as it gets.
Check driver support for the particular model you're considering first -- I don't know if it's still true, but in the past some ThinkPad models had hardware in them that wasn't supported in Linux.
