If I turn remote on first, then car like Duster says, I get the same results.

lets try the reset like I found in that hsp manual. Make sure you have the batteries (transmitter and car) fully charged, then turn on the transmitter first, THEN the car, then push and hold the reset button. Plug the motor wires in while it's off, and do the reset with it all plugged in and ready to go. I should also ad, just to be safe; I always set my car chassis on something (block of wood, or a stand) so the wheels are off the ground when doing this kind of stuff. Kind of annoying for it to glitch and drive off the table/bench.

I see that the motor/ESC combos from hobbypartz (thanks for the link) have a programming card.
I found one for $60 Leopard 1/10 Scale Brushless System Combo w/ Brushless Motor/ESC/ Program Card 9.0R 4370KV.

What do you think about that? Should I have any problem replacing the current parts? Will they fit in my truck?

Trying that now...

I tried this. It does not do what the manual states. After holding for 8 seconds, then a second time for 15 seconds the esc light does not change.

After examining all the parts I noticed there is a transmitter in the truck labeled
R-07 27.125MHz. There is also a similar transmitter in the remote labeled T-07 27.125MHZ. Do those need to match?

The transmitter is what you hold in your hand. The box in the truck is the receiver. They match. It's not the radio that's the issue, I don't think, it's the esc (throttle), since you have steering. That combo on hobbypartz will probably work better for you, especially since it has the manual so you'll know what you're doing. I personally don't have any experience with that brand, I've only bought hobbywing stuff there, but there are others on the forum that have bought leopard stuff with no issues.
Since this is just a basher, there's no point in getting something more $$ or sophisticated. You could also just pick up a cheap brushed ESC somewhere, since there's probably nothing wrong with the motor you have. I'm assuming you wouldn't mind going cheap, considering the car you started with. Brushed escs can be found for $30-40, even by major brands (HPI, Traxxas).

HobbyWing eZRun-35A Brushless ESC for 1/10 Car (Version 2) w/ Reverse programming

what about this part. ~$30 plus ~$7 for a programming card?

The programming card is a nicety, but unneeded. Almost all brushless esc, including the hobbywings can be programmed (drag brake, throttle punch, reverse limit, etc.. ) via the esc and audible tones. I have an LCD programming card, but haven't even used it yet. You don't need a programming card to setup the esc initially.

I have left the RC car charging for the last few hours and I was able to get the car to go once I adjusted the trims on the remote. I was only able to go about 30 seconds before the car got all "choppy" and the car stopped and I had no control at all.

So, I have a couple of questions.

1: Will replacing the ESC fix the kinds of issues I have been having?
2: Should I replace the NiMH battery with a LiPo?