Matt,
You can build a machine for under $1,000. You'll have to look around a little and decide which design fits your needs. Once you've decided what you like, you can start looking for postings from others who have built it. This will help you get around some of the more common problems.
I tried to shave cost as much as possible in mine. If you know something about electronics, you can build your own power supply and driver. I bought the driver as a kit and built the power supply from an audio power transformer that I scavenged from a "dead" receiver amp. You have to make sure your transformer will handle your intended amp draw. I bought my motors from Probotix and the stepper driver is the Linistepper. I was able to get an old computer for free and the rest is a combination of donated and purchased parts.
I have 3 kids and a small budget, so I started mine 2 years ago in March and finished around the end of September, 6 months later.
It's a lot of fun, especially when you get it done and can start cutting and learning. Hope this helps!
My Solsylva machine (my first cnc)
http://www.cnczone.com/forums/showthread.php?t=44336