Android 5.0, or 'L' requires explicit intents.
It appears that the bind service call fails on Lollipop because of an implicit intent being used instead of an explicit intent. I am not a Java developer, so this all sounded like voodoo to me. I looked about for ways to find explicit intents, found stuff about ResolveInfo, PackageManager, even found this nice website explaining what was wrong (but not literally how to fix it) Dealing with L Deprecations: bindService()
After a bit of hacking around, I finally found enough info in one of the stack overflow answers and implemented the final fix.
I feel like I hunted for quite some time before even knowing how to find out exactly what I needed to do to modify the google example code so that it worked. Here is literally how I have modified LicenseChecker.java in order to make it work in my project: