I spent quite some time looking for camera bags as well. I originally wanted one that could hold all the lenses that I'll get in the near future, but realized I would never carry such a large bag as a walkaround bag. I ultimately settled for the Lowepro Nova 1, because I had a Dell coupon and Dell had a limited set of bags available. I'm actually quite happy with it, as it could probably fit my Rebel XTi with attached Tamron 28-75 and a Canon 70-200 F4L, though it'll be a tight squeeze. This bag is probably no bigger than your original though and will not fit an attached grip (maybe if it's separate).
For a larger bag that's cheap, I would probably get the one HuskerTony is eyeing (Canon 2400
, linked for pictures). It actually would cost less than my Nova 1 if I didn't have the Dell coupon.
If I had the money to spend for a larger bag, I'd probably get the Lowepro Slingshot 200
. I like the idea that you can access the camera without having to take off the backpack.