Hello Colin,
if I have understood your issue, you see the '*' only in some cases during time periods of low performance on the MPLS service.
As suggested by Narayan routers within an MPLS cloud need a specific configuration to be able to answer to traceroute probe packets.
A possible interpretation is that when you face issues the provider has has troubles on the normal path they use and your traffic is rerouted via another path where:
two routers can have different settings regarding ICMP unreachables or they are too busy with links saturated and other cpu intensive tasks and they don't answer.
Also service provider routers can have the control plane policing (CoPP) configured as suggested by the other colleague and one possible effect is that they skip to answer with an ICMP unreachable to your traceroute probe.
You should compare traceroute results in good conditions and during issues to see if the number of hops change of if any of the IP address changes this would mean your traffic is taking an alternate path.
If the path doesn't change CoPP on SP routers can explain this and it can be seen a sign of great activity in the signalling plane that may lead also to performance issues.
Hope to help
Giuseppe
