Best advice is same as always - get into the shops and start having a play with models from different manufacturers. Nikon, Canon, Pentax, Olympus, Sony, Sigma - all do models in your price range, even with lenses in some cases. So, start picking them up and seeing which ones you like the feel of in your hand, which ones you think have the better controls/menus for you. Remember that Nikon and Canon wil have the largest range of accessories/lenses available as you build your kit, but brands like Pentax and Olympus will have similar bells and whistles at a lower price.
Once you have decided on brand, then start some online surfing for better deals than you might find in the high street, and indeed at reputable s/h dealers.
Personally, with that budget I would recommend a Nikon D80, as a Nikonian myself, but the final choice comes down to what you like. Also have a browse of the For Sale section here and see what is up for grabs, especially from those members that have just had a christmas prezzie upgrade.
Good Luck! You wont regret it, even if your bank manager/credit card company learns to hate you pretty quickly.
