Android LVL - NOT_MARKET_MANAGED

I am trying to set up Google Play licensing with my app. I have followed the documentation precisely, yet I still can't get it to work:

the LVL library is the latest version available in SDK Manager
I copied the license check implementation exactly from the sample app
I copied the BASE64 key of my app from "Services and APIs" in Google Play to the BASE64_PUBLIC_KEY field and made sure countless times it was copied correctly, contained no white spaces
I uploaded the app to Google Play as alfa, also tried uploading it as beta and production draft
I tried running the same compilation of the app both signed with a debug key and the key with which I signed it for Google Play(the exact same apk)
I tried setting different static test responses on Google Play

Every time I run the app on any device where I'm logged to my developer account, I always get NOT_MARKET_MANAGED error. I've read through countless forums but none of the answers helped. What else can I do?

Solution

I had the same issue and I found this note on developer.android.com:

Note: Previously you could test an app by uploading an unpublished "draft" version. This functionality is no longer supported; instead, you must publish it to the alpha or beta distribution channel. For more information, see Draft Apps are No Longer Supported.

Here's what I did:

Signed and uploaded the apk file. I uploaded as beta, but I don't think it matters.
Published the app. Note, I didn't promote it to production. I used the dropdown in the top right corner. You may see the option "Why can't I publish" and no "Publish" option. If you click "Why..." it will explain what you have to do first. In my case I had to upload at least 2 screenshots.
You can unpublish straight after publishing using the same dropdown.
Give it a good few hours, may be a day.

Next day my app started to receive responses according to my "Licence testing" setting in the developer console.