I had this problem, also, and here's what worked for me:
1. Cancel the downloads and/or uninstall the apps of concern.
2. Go to your phone settings and set the date+time to update manually.
3. Go to your email+accounts and force your Microsoft account to update/sync.
4. Return to the store and retry the download/update.
You may try restarting your phone before #2 or before #4, but in my case I didn't have to restart my phone. You may also to go straight to #2 without tapping on "Attention required". Let us know if this works for your as well.
The things that did not work for me:
restarting the phone
performing a soft reset
changing the region (to my actual region... must... have... Cortana)
uninstalling the app
retrying the update/install 36 times
threatening the phone
P.S. I asked TrueCaller through Twitter about the problem - they have redirected me to a TrueCaller help, but that isn't necessary at this point since the problem might be from Microsoft's side.