This is a tough call without having multiple batteries to use for testing. I always suspect the battery first, since it's generally the most likely problem. There are a lot of flaky batteries in the world, so it may be that your "new" battery is not actually good. I would have it swapped out before doing work on your computer, just to see. Also, how is the behavior of your old battery? Does it behave similarly, or does it charge like you would expect it to (although of course it probably doesn't hold much of a charge, which I assume is why you replaced it)? If it behaves like you would expect a battery to, then that points to your new battery having a problem, and if it behaves strangely like the new battery, then your laptop may have an issue.
I'd Google "Coconut Battery" and download it, and see if it shows that it is charging, and verify the capacity of the battery is what it should be. I would also make sure to leave the battery charging in the computer overnight. Sometimes batteries that have been sitting for an extended period take a while to "wake up" and normalize themselves.
It's conceivable that the battery connector inside the computer is faulty, or that you have a bad DC-in, but that's rarely the case in a specifically battery-related issue, especially if your computer works fine on AC power, and I'd really explore testing the machine with other batteries first if possible.