That's a good budget to give you a lot of great options.
1. Steel frame 26" wheel hardtail with kick ass component spec... not difficult to get this thing well under 25 lbs. You can find a used steel frame without too much difficulty, and they last forever. Mine is still rocking out at 10 years old! And if you're building from a frame, try to buy a build kit as opposed to individual components, you'll save a lot of money. Sometimes you can find year old XTR groups for ~$1k online!
2. "Entry level" dual suspension cross country race bike. Entry level is in quotations because this type of bike is not really for recreational riding or beginners. The component spec is usually lower end as in LX or X7... but you occasionally get some XT or X9 bits. Sometimes there are generic parts too though, but they aren't the end of the world. Frame geometry and even composition are the same as the more expensive models, except for when you get into the carbon series'. Suspension has come a long way in the past few years, and there aren't many duds anymore. The difference between lower end and high end is usually mass and some features like lockout. DON'T buy a lower end dually XC racer with the idea of building up the components over time... very costly and you're better off shelling out more quid now.
3. Used high end dual suspension XC racer. There are a thousand online articles on things to look for in a used bike. Check them out and you'll save yourself some grief. Don't be afraid of this option, lots of people replace their bikes every other year, or even every year so it's quite possible you'll find a gem. Look for XT, XTR and X9, X0 components in this price range... tubeless wheelset would be nice too! Also consider that you'll likely have to replace at least a cassette and chain unless it's already been done recently. (Add ~$100)
4. 29er. At that price point you can get yourself on a pretty sweet 29er with a solid build. See here for some more 29er notes:
http://www.ar.attackpoint.org/discussionthread.jsp...
With any of these options, make sure you get to try them out as much as you can. It's not hard to find someone who has the same bike you're considering to try theirs if your shop won't let you give it a real whirl.
If you've got any specific brands / models in mind, do let us know!