I also was in the market for a camera, also on a budget. I would look at used and go with a DSLR.
I picked up a Canon Rebel 6.3 MP stock lens, 70-300MM macro lens, add on flash, 2 1GB memory cards, 2 filters, 2 batterys, all the factory stuff and some other things. I picked this up for 500 on criags list. I would just look for a good deal.