This has to be due to you running too much longitudinal
current through the cell's piece of the bussing. It ought
to be nigh impossible to fail electromigration with only
CMOS gates, unless they are all thrashing at high speed
and your standard cell library uses -really- skinny power
bussing (which is a bad idea for other reasons as well).
Don't see how labels have anything to do with how
many vias you can put down. Nor with simply adding
bus width on the present level (although this might
entail you actually touching the layout, not just
taking what the autorouter spits out).
I suspect that the construction of the power supply
mesh has not received due attention.