Sup guys. @Awks
I came across the same bug on my Nexus 4, too.
Tried the following: wiped cache, wiped play music data, fiddled around with lockscreen security settings. No luck.
Then, managed to fix it.
I had this one app, called JAYS Headset Control, that allowed to assign functions to headset button clicks. I simply uninstalled that **** and now s'all good.
So beautiful lockscreen with album art & all: https://db.tt/HfD6m3ds
Too bad I now have to re-download my 3GB music library, d'oh.
So if you have any similar apps, be aware that they might cause trouble. Ditch them.
Cheers! Hope this helps.