Apps are generally installed in the data partition, which is a different partition than the internal sd. Check to see if your data partition is full. If it is, try moving some apps to the sd card and uninstalling any apps you don't need. If it's not full, try clearing the cache and data for the google play store and google play services, and clear cache and dalvik in recovery.