Alas, the problem is likely not the contacts app that came with the phone. It could be a flaw in the phone's system itself. Depending on what OS it is and what preinstalled things the carrier/service provider and the manufacturer have put on it. However, I can't recommend any specific other one.
I have to say, other than a flaw through what I mentioned above, issues on google's end or user error, I have not seen any major issues with the standard contact apps. Even in the newer versions of Android.