When you buy a new lithium-ion battery they are usually only charged to about 40% and if it has sat on the sellers shelf for awhile it may have discharged even more. Did you try giving the new battery a good charge? If this type of battery sits to long and discharges to a voltage below 2.9v it has a protective circuit that will put the battery in sleep mode, and the battery has to be boosted to wake from the sleep mode. I would have guessed this was the problem but it sounds like the battery was able to run the phone for a couple minutes before shutting off. Most Li-ion batteries may power on a phone at 3.4v but it will shut off within a minute or two because that is not enough voltage to run the phone. Below 3.3v the phones battery would appear to be dead until charged. The nominal voltage of 3.7v-3.85v is what most Li-ion are rated to run at and charge to 4.2v-4.35v at a full charge. If it falls below the nominal voltage it may power up but probably won't stay on long.
So what I am getting at is if the battery is not holding a charge of around 3.7v and is dropping to 3.4v or lower then the phone would show symptoms like what you have described. This could indicate a battery that has had a long shelf life in a hot or cold environment, or its possible you where sold a battery that has been used and was sold as new, or is just faulty. If you have access to a multimeter and can test the batteries voltage that would tell you if the batteries voltage is in the right range. If you can exchange this new battery for another one I would try that first.
If not then maybe try doing a soft reset and if that don't work try the hard reset.
Hope you get it figured out.