Go into the SDK Manager and install the Android SDK Build-Tools in the Tools folder.
This is new to SDK revision 22. In the update text for rev 22 is this:
• Changed the structure of the SDK by adding a new build tool SDK Component, which is based on the existing platform-tools component. This change decouples the build tools versions from the IDE versions, allowing updates to the tools without requiring an IDE update.
Because of this update, the tool to build APK's was not included in your SDK update, since it is now a standalone item. As such, your APK would not have been updated, but would still install since it had an existing APK already built.