At what amperage are you charging the battery? Be aware that charging at higher amp ranges will not fully charge the battery, and can result in a "surface charge" which will fool modern electronic battery testers. I have seen instances where the tester will show 100% charge, then with the battery left to sit overnight on the shelf it would show only 20% charge the next day. To avoid these false readings I use an old fashioned "load" tester first to deplete any "surface charge", then the electronic one to reveal the true state of the battery. All of this can be avoided by using a trickle charger, charging at 1-2 amps for at least 6-8 hours or overnight. Ideally, use a charger that automatically shuts down when the battery is fully charged.
Having said all that, you need to find out what discharged your "new" battery in the first place. You say the battery terminals are new, but what about the cables? Check them for cracked insulation and corrosion, and double check where they attach at the end opposite the terminal. A bad ground or corroded cables (or both) can cause a high resistance condition, which can drastically reduce the amount of power available at the starter. When combined with the above described "surface charge" condition and perhaps a starter solenoid nearing failure, this could cause the symptoms you describe. When the battery goes dead after five minutes, will it still run the lights and accessories or is it truly dead? Have it tested in this condition instead of charging it first. Good luck.
