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 to compile the svn trunk version. (just make && sudo make install)
there was a bug in trunk which draw it unusable after r3402, but it was fixed again so you can use trunk normally.
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 is good since several releases already.