You should test the battery, make sure it is 3 volts or more. ("New" doesn't necessarily mean "good"
I always test batteries with a multimeter...)
Did you get the correct battery? Should be a CR2032.
The label side (showing the battery type/etc. I will call that the "top" of the battery) should be facing out. Make sure the battery edge is contacting the vertical contacts inside the battery holder, and that the "finger" is not just "close", but actually in contact with the "blank", or bottom side of the battery. "Close" means nothing unless the contacts are actually touching the battery. It probably is completely normal to wiggle around a little, just look closely to make sure that the battery edge, and "bottom" of the battery are both touching the contacts.
Be careful - that "finger" can be quite fragile if you need to bend it slightly to touch metal. DON'T bend that tab, unless you are completely sure that there is no contact. If you can see there is no contact - remove the battery, then bend that tab (slightly) toward the holder, then insert the battery. If no contact, remove the battery, and try a bit more. The only adjustment that you will need is just enough to contact the battery, and you can't really adjust that while the battery is inserted. Adjust, THEN insert the battery to try it out.