Nevermind my last post about what kind of macbook. I am just gonna assume its a MacBook Pro since you said "latches". This usually happens because of the battery swelling and pushing against the sides of the slot where the battery is. In the past i have solved this issue by pulling both the tabs at once and taking a spudger which is sold on this site, you can also use anything that is a dull plastic (do not use anything sharp it is a battery and that could be dangerous) and pry in between the case and the battery. The side of the battery nearest the latches with be the part you want to pry on which i assume you know since you said you have replaced the battery before. Let me know what you get.