Can a brand new battery be bad?

Did you replace the battery as well? If both cables are badly melted it is likely the battery has suffered damage as well. Do you have access to a Multimeter? Set it to Volts DC. With the engine OFF put the red pin to the red positive battery terminal and the black pin to the black negative terminal. If the battery is good you should get a reading of around 12.6 volts or higher. Anything below 9 volts and the battery is probably worn out or damaged.
You will also need to find out what caused the cables to melt. There is most likely a 'Resistance' issue somewhere in the electrics. This is where the voltage is restricted and cannot flow correctly. This generates heat and is possibly the reason the cables melted. Have you 'Jump Started' the vehicle recently? Connecting jumper cables the wrong way around can have a similar effect.

I ran into a similar problem with a Cavalier, turns out that the on-board computer needs to have constant power. Even if the battery is very low or even dead, it still has to be connected. If the battery is removed it breaks the circuit and stops the command that lets the engine start. After the new battery was installed it would crank but not start, the dealership told me that I had to have it towed to them to have the comp reset, which would have cost around $150 total. Thankfully a mechanic friend of mine had a diagnostic machine and was able to reset it for me - cost me a case of beer. He then showed me a (not so simple) trick around this for the future. Once it is running again remember this. 1 Have the new battery and jumper cables ready, 2 Loosen the battery terminals on the dead battery but DON'T take them off. 3 Connect jumpers to the car battery cables and to the new battery, like you were jump starting from just the new battery. 4 Remove the terminal cables from the dead one in the car and remove dead battery (be careful not to let them come off the cables OR the good battery) it's OK if it disconnects briefly, but reconnect it A.S.A.P. 5 Put the new battery in and connect the terminals BEFORE removing jumper cables. Once they're on the terminals just take away the jumpers and tighten the nuts. That's how you change a battery without letting the car ever lose power. Hope that helps Jose. Good luck, safe driving. Grimm

If you're jumping with the jumper neg lead on engine block (like you should) then you have a bad ground lead.
If you are jumpering to the battery terminals then the connection to the battery itself is bad. Clean the battery connector terminals.

Bad connection on cable ends or where they connect to battery. Quick check is if you have a good set of jumper cables, use the jumper cable as a replacement for what maybe the defective one. Hook negative cable good to battery neg. post and then put other side on neg cable to engine ground on block. See if it cranks, if it does than the trouble is on the neg. cable. If not then put positive cable on pos. post of battery. Then put other side of pos. cable on the starter post, try to start. If it cranks then the trouble is on the pos side of cable. Hope this helps.

preferably put engine on a stand, with flywheel on and starter motor installed. take a battery and a pair of jumper cables and hook the positive end to the big terminal on starter and a small wire to small terminal thats toward block. then touch small wire to battery positve to engage starter, engine should crank over.

bad connection from the terminal youll need a battery jumper cable. But first lets try this make sure battery terminal is tight and clean okay next now we are going to find the weak link. Take the negative battery cable and the jumper on negative cable on battery and put the other end of that cable to body ground there we made a better cable ground connection. ck to see if problem solve, If yes correct negative terminal. If no problem in positvie section you need to make sure positive is clean contact.

Your jumper cables are most likely red and black. Locate the positive and negative terminals on your battery, they are marked ( + ) or pos.,that's the red one, and ( - ) or neg. that's the black one. Conect one end of your cables to your battery (doesn't matter which one you do first) make sure you are connecting the other end to the same terminal on the dead battery (that is to say positive to possitive) now do the same with the other cable. There may be a little bit of a spark that's normal when you make the final connection. The danger is in taking them off, do it in the same order that you put them on, if you take both cables off at the dead battery and they touch you are going to be having a bad hair day. the thing that most people don't get is you have to have a good clean convention. If you don't try wiggling the clamp on both batteries to make them dig into the terminals. Also there is a huge difference between someone who left the lights on in parking lot and someone with a dead battery on the side of the interstate. The guy in the parking lot has a dead battery, the guy on the side of the road has a dead battery and a dead alternator, he needs a tow truck, not a jump.

The battery should be on the right hand side of the car, in the engine compartment, remember when you jump start it to hook up the jumper cables like this; negative jumper cable to negative battery terminal on your car, then positive jumper cable to positive terminal on your car, then, put the other positive jumper cable to the car that's jumper car and last connect the other negative jumper cable to the jumer cars engine block, and that should help you.

with a new starter, this sounds like a bad battery cable or terminal end. the easier way to figure this out w/out checking the voltage drop across a whole battery cable is to affix the jumper cables strategically to find the bad one. Put jumper (+) on batt (+) and jumper (-) directly onto a piece of unpainted engine metal and not in the way of moving parts. If it starts this way then you've got a bad ground cable. If it didn't start, put jumper (+) on the hot post of the starter solenoid (there are 2 posts, only touch the one w/ the fatter cable going to it) or on a remote jump point if equipped, and put jumper (-) to batt (-). If it now starts you need a positive battery cable, or just a battery-to-starter cable (if separate)