And one last update, sorry about the three posts in a row. I noticed that the malleable VI common to all the VIs failing the build also called malleable VIs within itself (part of the same set). Apparently it doesn't mind building malleable VIs, as long those malleable VIs don't contain other malleable VIs.
Luckily for me, in this case, I only had one level of embedded malleable VIs. I solved the issue by replacing the embedded malleable VI its contents (it was a pretty small VI so this wasn't disruptive on the BD). I imagine it this could be a larger issue for someone who built a highly embedded malleable structure and wanted to try and build a package.
Is this a bug or is there something about malleable VIs that make them incapable of being built into packages?