If you want to try something before dropping the new battery cash, remove the negative cable ( BOTH ENDS ) and make sure you have no corrosion.
Also clean the positive battery terminal and cable for the same reason.
Then hook up a multimeter and have someone try to crank it, if the voltage drops like Max said ( and Advance's test also says you have a bad battery ),
then go ahead and get the new battery.

( you could also tell Advance / Autozone / Pep Boys / NAPA / O'Reillys that they can put the new battery in, and if it cranks like it should, then you will buy it. )