Paradigm makes great speakers. The problem is, a whole 5.1 set is out of this pricerange. You don't get much in the way of speakers when trying to do a receiver and 6 speakers for <$500.
If you do want to 'upgrade' past the kind of speakers bundled in these kits, Paradigm is a great way to go. And if you can get to Canada, the prices are cheaper (the dollars are the same, but it's in Canadian dollars $1US=$1.50Cdn) because they're made in Canada.
You can always do what I did, which is to get a receiver and only a few, but better speakers. I went:
Yamaha RX-V496
B&W DM302 fronts
B&W ASW500 subwoofer
My listening position is such that I don't really need a center channel right now, but will add one later. For rears, I use old bookshelf speakers I had laying around, but I only use these for movies, never for music (they sound completely different from the fronts)