The current budget receiver that's generating good reviews is the Onkyo Tx-SR605 and can be had for around $400. Add a sub from SVS or HSU for anywhere from $200-$500, depending on your preference for bass. That will leave over $1000 to choose your speakers. You should go out and listen to speakers yourself to find the ones that sound good to your ears. Alternatively, you could take the recommendations of many here who like the internet brands, like AV123, Axiom, Ascend, etc.
edit: or do what Greg said and dump the whole budget on one really good subwoofer.
re-edit: What is the existing sub?