I'm using exactly the same control as you, I have built a sample that puts icons on the map.
In your sample, the icon overrides the labels on the map. In mine, the labels override the icons, causing them to disappear seemingly randomly, but they are really getting overwritten by labels on the map.
I've tried different Zindex's as high at 11 with no success. (your Windows Phone map icon is set to 5).
My sample uses a hub control and looks up the map control at runtime via its "Loaded" event handler, but other than that, I don't see a difference.
I'll also report this in the forums, but haven't seen anyone else with this problem, so I thought I'd just remark here since you have a sample that works and is for WP 8.1
A little misleading at the beginning. Jaime talked about the 7712 release and that there was another drop coming, but he is confusing the phone software and the SDK. The SDK RC came a few days ago, and I was told there is no dev version after 7712. After that, the next step is production Mango. As I understand it, devs have to restore their phone backup using Zune and then Zune will tell them that there is an update available.
Now, all we have to do is to cut though the carrier red tape that left NoDo "testing" for a month or more, and we'll be doing well. I for one am hoping for production Mango (with some updated drivers for my LG Quantum) in October or earlier.