We had a similar issue recently. This happened to us when there was Nortel equipment in between two pieces of Cisco gear and I think it is caused by Cisco-proprietary communications.
Cisco-1 had a VLAN on a trunk. Then there was a Nortel box. Then Cisco-2 was connected to the Nortel on the same VLAN, but as an access-port. The problem is that Cisco has a proprietary extension to STP and attaches VLAN tags to the STP BPDU. The Nortel doesn’t recognize this Cisco-only extension and just forwards the BPDU without removing the VLAN tag. This means that when the frame gets to the other Cisco, there is a miss-match because the BPDU has a tag but Cisco-2 is configured as an access-port and it doesn’t expect there to be tags. The Cisco-2 port therefore shuts down.
In our case we just turned off STP on the trunked Cisco device. One possible way to workaround this in your case might be to configure ALL connections between Cisco and Nortel as trunks, perhaps using a dummy VLAN. In this way, there will not be a mismatch with VLAN tags on the BPDU.