I have similar issue using this Walkman app. Seems to be syncing but whenever i try to access the walkman app on the watch, it looks like it's starting but nothing happens... Weird.
Yeah I thought I'd solved things with the Walkman app but my playlists kept disappearing. I tried to use Play Music several times with no luck. When I would select a song/album in the 'manage wear downloads' section it did nothing. Then recently/finally I decided to create a new playlist and add songs to it. After I created a playlist it appeared in the 'manage wear downloads' and miraculously it synced when selected. I've since created 3 playlists and all have synced. Songs/albums don't work for me, but playlists do, go figure.