DSLRs: Pentax KX, Sony A500, Nikon D3100 - all should be available around $500ish, and get you a 2 lens kit for your budget. Sony A33, Pentax KR, Canon T3 - will stretch the budget a bit - maybe restrict you to one lens - but still be worth a look.
Mirrorless: Sony NEX3, Panasonic GH1, Samsung NX100 - should easily fit in your budget with 1-2 lenses, and room to spare for a few tidbits. All would actually be a bit better with video than the DSLRs due to the ability to quickly autofocus during video, which DSLRs cannot do (save the Sony A33/55, which both can do extremely fast focus during video). These are smaller, lighter systems than DSLRs, a wee bit slower when it comes to focus and tracking which will only affect you if you need to shoot action or wildlife. They are far better than any P&S camera in high-ISO shooting capability.
Prosumer/advanced P&S - Canon S95, Panasonic LX5, Canon SX30, Sony HX100 - just to name a few. These range from the cameras with less lens range like the S95 & LX5, but bigger sensors and more control, to ultrazooms with smaller sensors but huge lens versatility with massive zooms. None will be great in low light, all will do a respectable job with video, and all will be fine for most types of general photography.