I would check the battery cables and the inline fusible links or large fuses for battery. The battery cables should have a tight metal to metal corrosion free fit. Look in the underhood fuse/relay box and you will see a diagram on top cover indicating battery fuse and starter relay. Check or replace them.
Even though the battery is new you might want to have it tested. See how much voltage it pulls when starting. If voltage drops below 12 then there is some issue.
I think it may also helkp to go though some of the steps in a dioagnostic walk through we have for this situation. I may give you 2 of them since there is information in each that may apply.
Always remember that Advance Auto ro Auto Zone will test batteries, pull trouble codes and loan out test and specialty tools as you go through these. Just use the links below;

http://www.2carpros.com/articles/everything-goes-dead-when-engine-is-cranked

http://www.2carpros.com/articles/rapid-clicking-sound-when-starter-is-used

Answered by DrCranknWrench (expert)
3,292 answers provided

1ST THING SNATCH THE BATTERY OUT HAVE IT FULLY TESTED AT A POPULAR AUTO PARTS STORE.....SEE PIC 1

WHATEVER THE DEAL IS---RE-INSTALL "YOUR FULLY CHARGED BATTERY" OR YOUR "NEW FULLY CHARGED BATTERY"

IF IT FIRES UP....GREAT!

NOW LETS TEST THE ALTERNATOR---MAY BE THE REASON THE BATTERY WAS DOWN

HERE'S 2 WAYS TO DO IT

http://www.youtube.com/watch?v=Bzz7P3qNHcE

THE OTHER WAY IS TO IMMEDIATELY GO BACK TO THE AUTO PARTS STORE WITH YOUR CAR....HAVE THEM FULLY TEST THE CHARGING SYSTEM...ALSO USE THE "AMP CLAMP" TO SEE IF YOU HAVE A "PARASITIC DRAW" (THIS PARASITIC DRAW 'THING' CAN BE FOUND ON "YOU TUBE" ALSO)

NORMALLY THE AUTO STORE WILL PERFORM BATTERY AND CHARGING TESTS FOR FREE!!!!

ALL RIGHTY THEN......GOOD BATTERY.....STILL NOT WORKIN'?

LETS SORTA GO THRU THIS.......THE "DRILL SERGEANT" PART IS WHAT I WANT YOU TO PAY ATTENTION TOO

http://www.2carpros.com/questions/1996-chevrolet-tahoe-wont-start-sounds-dead-battery-jumpbox-get-same-reults

ONE LAST THING.....'FORE YOU GO OUT AND BUY SOMETHING EXPENSIVE, I MAY CAN SHOW YOU HOW TO SAVE

SIFT THRU THIS, TILL YOU FIND MY ANSWER AND PIC

http://www.2carpros.com/questions/2001-kia-rio-brand-new-duralast-gold-battery-won-t-hold-charge

KEEP US POSTED (YOU VERY WELL MAY OWE ME LUNCH!) LOL!

THE MEDIC

Answered by CJ MEDEVAC (expert)
6,803 answers provided

battery is all good, but still nothing when i try to turn her over. relay is still clicking each time i turn the key though, and also noticed the abs, battery, and ebrake dash lights flick on for a seccond when trying to start?

Response from quackschuk
1 question asked

and by fuse/relay box do you mean the one under the abs module with the five relays in it? if so their is no diagram i could find

Response from quackschuk
1 question asked

HAVE YOU DISCONNECTED THE BATTERY, WAITED A FEW, RECONNECTED?

HAVE YOU CHECKED AND CLEANED CONNECTIONS ESPECIALLY THE BIG CABLES THAT BRANCH OFF OF THE BATTERY CABLES?

THE MEDIC

Answered by CJ MEDEVAC (expert)
6,803 answers provided