Sorry to hear about the story associated with your old stuff
HTIB = Hometheater in a box. Basically it would be speakers / sub / receiver (and maybe DVD player) sold as a package.
Onkyo makes decent ones
If you have the budget and desire for something higher end though, then go for it. I just wanted to make sure this was something you wanted to do. Some people would be perfectly happy with a $500 set (or even using the stock speakers in their TV *shudder*)
So... for your system...
For your sub, I'm pretty confident in recommending
SVS as an option for you. With 25 foot ceilings, that's going to be very tough to get good bass going. You might want to send an e-mail out to the guys at SVS with dimension of your room to get an idea of what you might want to get. They'll give you a no BS response to what kind of sub would be good for your room size. Unfortunately from the info you gave, I bet you could probably spend your whole budget on sub and still want more

(At least I probably would) I guess it certainly depends on what you're trying to accomplish though. If you don't care if you can get your hair moving, then an SVS PB10 / PB12 / 25-31 PCI would be a good choice.
If you're into woodworking, you might want to think about building a sub. I don't have the skills, patience, or tools to do it myself, but if you're into DIY, a sub would be a great first project. Much easier to do than speaker building (although that's not too hard from what I understand either)
For your receiver, pretty much anything from a decent company in the $500 range is going to be a good bet. Harman Kardon / Onkyo / Pioneer / Denon etc.
A few features that are making their way down to units in this pricerange are HDMI inputs and auto-equalization. I had auto-equalization on my receiver before I replaced it, and honestly I don't think it did a very good job. It seemed to mess up the timbre matching of my front three speakers (this was a Pioneer 1014tx).
Depending on what TV you get, you might not be running video through your receiver either. I'm sort of forced to due to having a projector across the room so I only want one cable running across the room. If you get a more standard set though, you might as well just send the video straight to the inputs on the TV. Your receiver will only have to handle audio if you do that.
Manufacturer specs are pretty much all over the place as far as power output goes. Pretty much anything in the $150 to $1000 range for receivers is going to give you a figure of something close to 100watts/channel (HK being one of the exceptions here). Don't base your decision off something like one receiver saying 100watts and another saying 110watts. With decently sensitive speakers and reasonable listening volumes you should be ok with pretty much anything in the $400 - $500 range by a good company.
Speakers are going to be a lot more subjective. This is where the biggest difference in sound is going to come from and where you're going to want to "invest" most of your money. If you can go out and listen to some different stuff, that would be great.
You'll get an idea of the kind of sound you like. It sounds like you have some idea what you want to hear, which is good

The most important speaker are going to be your front three. If you're going to skimp somewhere on your speakers, make it the surrounds. They don't do a whole lot during movies.
During movies your center is going to be doing something like 70% of the sound, so it's important to get a good one. For music, listening in 2.0/2.1 is probably what you want to be doing, so getting good main speakers is going to be key for good music listening.
For movies it's nice to have the front three speakers match for panning effects. Stay in the same brand and same product line for your speakers to get the most seamless sound.
If you can get out to some AV stores, check out some different stuff around your pricerange. Something along the lines of $300 to $500 a pair. Bring a few CDs of stuff you're familiar with and give some different products a listen.
Some stores will let you bring some stuff home to try it in your own room to see what you like.
I went through some retail demo-ing but ended up getting my speakers online. I think I got a lot more for my money going that route. I found a local owner and did a demo in his home. I liked what I heard and am very happy with my choice. I think I got something a step above the retail products I tried for the same price.
If you think you might want to try something like that, several online speaker manufacturers have forums where you could try to find someone in your area. If not, they will all give you a demo period to try their speakers before you decide if you want to keep them. If you don't, you can ship them back and get a refund. Depending on the company, you might lose the cost of shipping one way, both ways, or lose nothing at all (Aperion audio).
If I was doing this over again, I think I'd buy a pair of speakers from a few different online manufacturers and try them out in the intended listening environment. After trying them out for a week or two, I'd return the "losers" and then complete my system around the set I thought was the best. Kind of a lot of effort, but that might be the best way to do it to make sure you like what you're getting.
Ok, I'm rambling again
I don't remember how much of this stuff I wrote already in my General Audio Thread... it's been too long since I wrote it heh.
I do remember that I wrote down some brands to look at in there, so that might be a good place to check.