Thanks a lot Bob for your response.
I had tried this for past 3 days and it did not work (WMP 10) but today after downloading Windows Media Player 11 somehow something changed.
MTP mode, navigate to the Music folder –> generate playlists by right-clicking & Create Playlist worked for me finally
Also another thing I notice is now I can drag and drop songs from one folder to another on the device itself. I was unable to do that before!!
Let me play around with this some more and see what else I discover.