I would first verify your MSTP configuration to make sure it really is configured properly. MSTP can be tricky to set up and configurations between switches require certain things to match, such as the Name, Revision Level, and VLAN-to-Instance mappings. One of those things not matching on any switch in the MSTP region will cause MSTP not to work properly.
Additionally, I would make sure that you don't have any switches on the network that might be using another form of spanning tree, such as PVST or RSTP. Different versions of spanning tree on the network can cause strange problems like this, too, since they all have slightly different methods of transmitting BPDUs and/or different BPDU formats.