I'm running a sub-200 USD Acer Aspire One laptop right now on the latest version of Ubuntu. This laptop has a single-core Atom 450 -- not a fast processor. In spite of this, it runs Ubuntu very fast. I did put in an extra GB of RAM (it came with 1 GB), but I think that it would have even run well with 1 GB of RAM. The only time I even notice the operating a delay is when I load up a bloated web site, like AT&T. This computer runs faster on Linux than my other computer, a multicore machine with much faster processors and 8 GB of RAM, runs on Windows 7 (I have to dual-boot that one for work-related reasons).
Honestly, you can't go wrong. Even the cheapest modern laptops run well on Linux. But I've been very happy with my Acer Aspire One. If you're OK with netbooks, you can get the Acer Aspire One with the dual-core Atom n550, or else the new AMD C-50 with a nice on-die GPU, for around $300 direct from Acer, I think. A comparable Asus would be another good choice. Otherwise, Dell makes some "full-size" Inspiron laptops that run well on Linux in the $400-500 range.