Installed app got replaced with the Andy Android icon and doesn't start Backstory: I went to pick up my phone to play Clash of Clans. The icon was the Android. When I tapped on it, it said, "app not installed". I went to the app menu and it disappeared.

What causes this issue?

Other info: I took out the SD card, could this have contributed?
Yes, the most likely cause here is that you removed the SD card and the app was installed there. Some apps can install themselves, or a portion of themselves, to the SD card even if it is external storage. 

When an application is removed incorrectly, such as removing an SD card that the application is installed on, what you are experiencing is a typical behavior... The icon on the home screen is replaced with Andy, the app is removed from the app drawer or replaced with "Andy", and when attempting to start it the exact message you stated is displayed. 

After manually deleting the icons,I would recommend clearing your cache then reinstalling the app without the SD card installed (if you wish to continue to have the app).