Thinkpad all the way!
My X40 runs debian very well, since IBM supports linux relatively well. Mine has the Atheros a/b/g wireless card which works perfectly with the madwifi linux drivers. Took a while to get the config right initially, but I use it every day. Most centrino based laptops should also work ok now. This wasn't the case when I got mine (nearly 12 months ago). Check
http://www.linux-laptop.net/ for details before you buy.
If you are new to linux I would recommend ubuntu, since it is debian based but much more friendly during install/setup. It also has a great community that has already answered nearly any question you could have.
