Nexus 6 - Pure Nexus
NotePro 12.2 64Gb
I post this in the hopes that it helps someone avoid a complete factory reset!
I know this thread is a little old, but I wanted to make sure to share this - my wife's recently purchased GS4 started doing this exact thing, and a reboot would also address the problem. There was an app running in the background not releasing its screenlock properly. The specific app in question was the Gameloft game, My Little Pony. I would suggest if you're experiencing this problem, start running through your list of recently opened apps in the App Manager and force stopping them one by one until you find the culprit.
Facebook app was causing this issue on my phone. One can check it out in Process stats in Development options