Okay, I thiiiiink I figured it out. I've made a build of my game 5 times with consistent success so knock on wood.
So if I understand it correctly, a FSM with an On Enter action automatically creates a On Enter Trigger component on the object, then is supposed to target the FSM in question that has it. For some reason, the objects that were having issue, did not link back to the FSM. The target FSM list was empty. After linking it, I've had no problems with the triggers not firing.
For good measure I updated the prefabs with what I assume were legacy scripts to make old On Enter actions work with updated versions of PlayMaker. I'm not sure what they were tbh. They were empty child objects that only appeared in the folder and not in the hierarchy when placed in the scene. Placing them in the scene and then applying the prefab got rid of them though with no issues after.
Don't know why it only broke during a build since it looked like it would be needed while playing in the editor as well though. That part still confuses me.