I recently went through a similar migration that eradicated proprietary protocols (i.e., PVST+, HSRP, etc.); our transition was focused on posturing us for a 'vendor neutral' network. Since you're running Cisco devices, you're likely running PVST+.
Cisco covers this in more detail, but the crux of it is fairly simple: establish a hierarchy and, contrary to what common sense would tell you, start from the core and move outward.
Set your priorities in a manner that cascades down. Base this hierarchy on what is closest to a central node. All nodes participating in this STP setup should be on a common structure, so for simplicities sake, manually set one root bridge with the spanning-tree vlan xx,xx root primary.
Once you're ready for the migration to begin, start with the core. The reason for this is because MST is backwards compatible with PVST, not the other way around. A PVST core won't be able to communicate with BPDUs from MST nodes; those trunk links will drop. If everything is going right, you'll see a small drop while the new STP protocol comes online and figures out the current lay of the land.
Then just trickle these protocol changes down all the way to your furthest nodes.
End-users might not even notice the small blip while MST elects a root bridge.
Rule #1: in a mixed vendor environment, one avoids use of vendor proprietary protocols
There are (apparently) several complications attempting to use VSTP (a Juniper protocol) with PVST (RPVST actually, a Cisco protocol) -- while they both run a per-vlan RSTP instance, they don't do it exactly the same (something about tagged/untagged native vlans, etc.)
Your best bet would be to use an open, documented standard with rules everybody obeys. That would be MST (802.1s, now part of 802.1q.) Of course, MST is a great deal more complicated to setup. (been there... complex hundreds of vlans across 4 vendors)
All this assumes the carriers aren't screwing with the traffic. If I'm following your description, the metro-e links are between juniper switches and the cisco's hang off the juniper's at each site. If that's true, there's only one path from a cisco to the other side, so mac flaps shouldn't be possible -- unless there's a pair of junipers at each end round-robin'ing traffic between sites. (or there are etherchannels that aren't setup/running correctly)
Best Answer
If anything it may just need to reconverge. About 45 seconds of interruption IIRC. If you can, while you are changing it on all the switches anyway, use rapid PVST. That will allow for faster convergence.