As it turns out there's nothing wrong with the font managers listed in the flex-config.xml file, and changing their order is not necessary.
Most errors occurring at compile time are due to a discrepancy between the "fontWeight" and/or "fontStyle" arguments and what the font managers find inside the Open Type Font files.
As it turns out, there's a single area within these font files where this information is matched, and it is the arguments of the "Styles (SubFormat)" string ID found in the "TTF Names" category.
In the MyriadPro family of OTF files, every single file uses either "Regular", "Bold", "Italic", or "Bold Italic" as the argument(s) of the Styles definition. Often, the arguments written in the font definition aren't obvious (eg. "Italic" only, for Myriad-BlackSemiCnIt.otf).
Now, this is totally undocumented, and how Adobe expect Flex/Flash developers to know what the proper arguments to use are for their fonts is anybody's guess. I used FontForge, an open source application running on X11 to look into the font files and find what the font managers are looking at.
I suggest that Adobe do either of two things: Get the font managers used by Flex to report precisely what they found as a discrepancy, instead of merely reporting an undefined error, or let users force whatever fontWeight and/or fontStyle attributes suits them when embedding.
P.S. - check out the discrepancy, for the same typeface, between the Weight definition and the Styles definition. Only the Styles definition is used by the font managers when embedding the file.