Every time I try to download the new update on Android, it goes through the process of staging the app, asks if I want to update the game, then it says "App Not Installed".

usually it means you need more space on your phone. the exact amount of space varies between versions.