Main symptom was that App was not showing up in Software Center even though it was deployed.
This one showed up in a couple logs with different messages, so here they are so Google can index them:
AppDiscovery.log
Expression evaluation encountered a fatal error (0x80070002).
CLocalAppHandler::DiscoverApp failed (0x80070002).
Deployment type detection failed with error 0x80070002.
Failed to perform detection of app deployment type Install(Install, revision 2) for system. Error 0x80070002
AppIntentEval.log
Rejecting ScopeId_9d0608fa-33a2-4479-bb1b-078d045f7274/RequiredApplication_c9bc4f8b-958b-4243-a9f2-36fe91daee65/2 due to evaluation error
ScopeId_9d0608fa-33a2-4479-bb1b-078d045f7274/Application_c9bc4f8b-958b-4243-a9f2-36fe91daee65/2 :- Current State = Error, Applicability = Unknown, ResolvedState = None, ConfigureState = NotNeeded, Title = My Broken App
ScopeId_9d0608fa-33a2-4479-bb1b-078d045f7274/DeploymentType_5d322e96-cd06-40e4-9743-bc090cba35be/2 :- Current State = Error, Applicability = Unknown, ResolvedState = None, ConfigureState = NotNeeded, Title = Install
Solution
Not sure how it happened, maybe the SP1 upgrade or a scripting issue. The app did not have detection rules, and therefore could not detect whether it needed to be installed. Seems as though 0x80070002 in Windows land is typically some sort of file not found error, but looks like SCCM might be returning it as a generic “I couldn’t find something” error.