I have investigated more deeply and I have found that “All Music” playlist which should reside in the “C:\Users[username]\AppData\Local\Microsoft\Media Player\Sync Playlists\en-US\00057566” is simply absent on Windows 8.1 while on Windows 8 it exists. And this is seems to be the root cause of the issue.
As I already mentioned on Windows 8.1 the problem exists only for predefined playlists and at the end of the day I have found out the following workaround which is seems to be working on the Windows 8.1. If you want to get "All Music" playlist just use the following code:
IWMPPlaylist allMusicPlaylist = mediaPlayer.mediaCollection.getByAttribute("MediaType", "Audio");
By changing "MediaType" attribute according to the table on the msdn you can get "All Video", "All Pictures" etc. predefined playlists.