Why does my MacBook Pro shutdown when the battery is between 50-30%?

My MacBook Pro 13" 2009 Unibody shuts down randomly. I purchased it from a friend. I noticed the battery needed to be serviced and the body below the keyboard would get hot, so I got a new one installed at a local Mac repair shop. New battery is great, low cycle count. Heat issue was better. It even charges up to 100% percent no problem. But when it is off the charger and goes down to say below 50% it will automatically shutdown. I plug the magsafe back in and it boots up. Sometimes I do notice it can get down to below 20% and then shut down. What do you guys think? A battery or logic board problem? Thank you in advance for your help!