Solutes added to stabilize nano-crystalline metals against grain growth, may segregate to grain boundaries and triple junctions where they can affect the process of the dislocation emission. We demonstrate that this effect can be very complex due to different rates of segregation at different interfaces. Moreover, at large concentrations, when the solutes form clusters, the interfaces between these clusters and the matrix can introduce new dislocation emission sources, which can be activated under lower applied stress. Thus, the strength maximum can occur at a certain solute concentration: adding solutes beyond this optimal concentration can reduce the strength of the material.