Did you use the clamp on style terminals? Why did you replace them in the first place?

With clamp on styles, the copper tends to oxidize and then you gradually loose electrical contact. Pre-made or solder on type are the best. You can have a good auto electrical shop do this, it should be reasonable in price and will help prevent problems in the future.

Another VERY common failure in a battery is a shorted cell.. As the lead reacts to the acid, particulate falls to the bottom of the cell within the battery and causes a short between the plates.

One other is a detached cell. When the battery is subjected to vibration it causes the the plates within the battery to separate.

The tricky part of these failures is when most people test the battery it will show a 12v output just fine. The secret to testing a battery is to test it under load, you will see the voltage and amperage drop off dramatically. With the above failures the battery will go from a 12v out put to a 9-10v output and have very low amperage depending on the battery make up. This usually will not start a newer vehicle but will look like the battery is fine. Only because when the load is taken off (ie. the starter), the battery will go back to a 12v low amperage state and act just fine.

We used to see a lot of people that would be wanting to replace their alternator because they had the battery tested (Usually by the "Chain" parts stores) but, not under load and they would be advised that the battery was just fine and it was the alternator that needed replaced... Not!

I guess the moral to this drivel is.. Make sure that you have the battery tested UNDER LOAD.

Not that this has much to help with your problem kpaske, but thought it somewhat educational.