Certain apps fail to update from Play, while others work
This was solved by going into /data/data/ and finding the appropriate folder belonging to the failing app. I found one with "swiftkey" in the name, deleted it, and following that the update worked just fine. Most likely, the app installation was failing in the background with INSTALL_FAILED_UID_CHANGED due to the app being restored with TitaniumBackup, as detailed in this answer.

So, in short, this seems to be an error caused by the UID changing between installs and Google Play throwing a fit, and it's solved by making sure app data is removed.