Saw
this one on Engadget the other day, seems to be getting some pretty good reviews. We were going to get my sister a replacement laptop for her birthday [more on that at the bottom], we're thinking about this one.
Dell Inspirons are also very good, and can be fairly cheap if you find a rebate or something (one of my mom's coworkers found some random combination of deals and got a totally spec'd out one for under $1000).
Do NOT get an HP. They're alright for PC's, but their laptops are abysmal. My sister, dad, and several friends have had serious problems with them (combined with terrible tech support). I won't get into the slew of problems my sister's has been plagued with; suffice to say that she's become so frustrated with it that she just goes on someone else's computer most of the time and I've decided that it would be more beneficial to just get a new one than try to fix/upgrade this one.
I second the Gateway advice, I've heard similar stories about ridiculous overheating.