We have located putative global minima for all lead clusters with up to 160 atoms using a glue potential to model the interatomic interactions. The lowest-energy structures are not face-centred cubic, as suggested previously. Rather, for N < 40 the majority of structures are decahedral or hexagonal close-packed, and beyond this size the structures do not correspond to any of the structural forms commonly found in clusters. However, these latter clusters are not simply disordered. High symmetry, magic number clusters are still present, the most prominent of which is the 148-atom D_3d hexagonal barrel. We relate these structural preferences back to the form of the interactions.