My apps status suddenly become "not installed on the phone", even the google play store!
I had the same problem. I fixed it by: 


shutting down my phone
removing the battery and SD card
putting it back 
turning my phone on. 


It's all there again.

If this does not work, try reinstalling the apps. 

Don't uninstall the apps with weird icon but go to the store and install them again.

No data will be lost!!! (Tried and tested)