Actually the Lenovo ThinkPads are famous for working well with Linux, but a great part of that compability is due to using Intel components. So what if you get one of the models with Ati chipset and Atheros WLAN?

WLAN

The version of madwifi in Ubuntu is too old to support the Atheros Chipset (AR5418 802.11abgn) and current svn is broken; you will see the networks, but you wont be able to connect.
To fix that you need will need r3402 or lesser and compile it yourself. (Just make && sudo make install)

Graphics Drivers

You can get 2D acceleration with both radeon and radeonhd drivers, but if you want to have 3D Acceleration, you will need fglrx, which is actually not that bad at all in the current version(8.3), you just have to enable

• Textured Video to accelerate Video playback
• Textured 2D to use the new 2D acceleration architecture

there is TexturedXRender too, but it is still quite buggy, so I would not recommend that.

to do so add the following lines to the Device Section of your xorg.conf:

Option    "TexturedVideo"
Option    "Textured2D"

this greatly improves 2D performance - the 3D performance was fixed several releases ago anyway