I think I have found a bug in the Android client that can be reliably recreated:
1) Open up the Android client
2) Choose 'Shuffle play' mode
3) Tracks will play randomly
However, none of them will be scrobbled. Watching the logfile on the server, each track is shown under 'listening to' as it is downloaded. But the server neither registers the tracks as 'now playing' nor 'submitted' with last.fm.
As a workaround, if you play any album first, then clear the playlist and go to 'shuffle play' mode, it will scrobble each track as intended.