HP laptops are often on sale for $400-$500 at assorted retail stores after rebate. Add RAM (they usually only have 256mb, but have two open slots), and you have a decent machine for under $600.
That, or buy a refurbished Thinkpad. My X40 cost $650 a few months ago; an older T-series laptop would be even less, and the build quality is worth the price hike. (I've owned four laptops in the past three years - an Apple, a Dell, a HP, and the Thinkpad.) Apple is a close runner-up, though; however, when I owned my iBook, they were still having chipset problems.
Speaking of which, if your wife is willing to use a mac, geeks.com has some excellent prices on refurbished iBooks, and good support, too. I purchased my HP from there, and when the factory warranty proved to be four months less than originally stated, they took back the broken laptop and gave me a complete refund in store credit, and offered to buy me a laptop that actually cost slightly more (but was completely useless for my needs - but would have been perfect for most folks.) While I have yet to use most of the store credit, being able to trade in a broken laptop for a giant flat-screen TV is always nice.
. I'd like to keep it as cheap as possible. I'm thinking like $600 or less. 
Facebook
Twitter