When I try to install, it prompts me to "update" as if the game was already installed, which it is not. If I choose to proceed then it gives me an error saying the package is invalid. 

That's weird, I'm not sure what would be causing that. The game launches fine for me and I don't even know if it would prompt you to update even if you did have a previous version installed, but I don't know if that's actually the case since I don't have an Android Phone. Is your phone an older model? Have you tried using other means to launch the game like JoiPlay? Are you able to launch and play it without hitting update?