If it's an old laptop, that probably means the "new" battery you got is old too. Li-ion batteries slowly self-discharge while sitting on the shelf. If it discharges below a certain voltage, the computer will refuse to use it. That's because Li-ion chemistry is rather unstable outside a certain charge/voltage range. Attempting to charge a Li-ion battery with excessively low (or high) voltage can cause it to catch fire or explode. This is what caused the spate of cell phone battery fires early on in their history. People were charging them with cheap knockoff chargers or 3rd party batteries which didn't properly monitor the voltage like the stock charger or battery did, causing the battery to sometimes catch fire. (Manufacturers eventually fixed it by moving the charging circuitry inside the phone.)
So return the battery for a refund. Probably not a good idea to exchange it, since if that store has had that battery sitting on its shelf that long, any others you get from the same store will likely have the same problem.