Why does my phone say "charging" when my battery goes down?

Replacing the battery was the smart thing to do as given the age of the phone, it was most likely at the end of it's life.

There is a possibility that your replacement battery is defective; there are lots of low quality batteries on the aftermarket. However, your phone appears to be suffering from fake charging. This is most likely a bad U2(Tristar) IC on the logic board. This requires a micro-soldering repair and is not a DIY fix. Your best bet is to find an experienced micro-solderer.

If you want to continue to do some diagnostics, you could try the following:

• If you have access to another, preferably known-good battery, then you could try that one.
• Is your phone recognized by iTunes and can you complete a backup or Sync of your phone? Not being able to do so would also point to a Tristar problem.
• Use a battery utility, such as coconutBattery (for Mac) or 3uTools (for Windows). It will tell you what the health of the battery is. If the software won't give you any details about the battery, it once again points towards a logic board issue.
• If you have access to a USB Ammeter, you could use that to determine if the phone is really drawing current when it says it's charging.
• Do a thorough visual inspection, preferably with magnification, of the area surrounding the battery connector. There are several tiny SMD components just above the connector. Of particular importance is FL11, at the top-left of the connector. If it is missing (which can happen when you pry the connector off), then the battery state does not get communicated to the CPU and this can also cause charging issues and fluctuating readings.