[privong]

I cannot speak to the $600 range, but I have had good luck with a Lenovo x201 – I have been using one exclusively with linux for the past ~4 years. Things pretty much worked right out of the box (using both Ubuntu and Arch Linux).

[Envec83]

I second that. I had troubles when running Linux on a HP and on a Toshiba laptop, but on a Lenovo one things have been working fine for 2+ years.