This is all good advice. I was where you were 8 months ago. Didn't quite have your budget but the same rules apply.
Take a handful of cd's that you know very well and go audition many speakers in your price range. Make sure the shop uses a mid level receiver with similar power to yours. Better amps and such will make speakers sound better than they will with your setup.
After I started this proccess I found it very enjoyable. The drawback is, the sales guy always plays you something above your budget that sound great and then you just can't settle for the cheaper stuff.

I always wanted the guys to name a few names intead of what I just told you, so....LIsten to everything you can but I might suggest- Paradigm, B&W, PSB, Quad, Wharfedale, and Focal. That should give you a bit to chew on.

There's lots of good "online only" brands as well.
Keep us informed and good luck.