System app was not signed correctly

My phone shipped with an outdated version of TouchPal. When I try to update the app through the Play Store, I get this error:

Package file was not signed correctly. Uninstall the previous copy of the app and try again.

The thing is: the app is a system app, therefore I can't uninstall it.

How can I get the app up to date?

My old phone had it preinstalled as well, and the update there went on without problems. What?