There are not Linux-native laptops for that budget.
I recomend you an Intel i3 computer, since CPU and GPU drivers are awesome and work like a charm. The bad thind about this is that an Intel HD graphic card isn't that good for video, music or photo editing... but will do the work.
Laptop dedicated GPU wich are what you need, doesn't work very good in Linux, at least new ones. New NVidia GPUs bring 'Optimus' technology wich switch between integrated and dedicated GPU to save energy, but doesn't work in Linux, you've to use a new proyect called 'Bumblebee' wich bring lots of headackes unless you like to tinker.
AMD/ATI GPUs have mediocre drivers and they rise your computer temperature/energy consumption unless it is a cutting-edge model.
In a 400$ budget there are some nice things like this one:
http://www.newegg.com/Product/Product.aspx?Item=N82E16834314007
Going for 300$ you've to drop to Intel Celeron or an AMD APU, wich aren't that bad either...
Regardless what you choose, you'll have to install Linux manually, but it is pretty straightfoward nowadays...
Good luck!