This was how things stood until 1984, when Shechtman et al. (Phys. Rev. Lett. 53 1951 (1984)), were measuring the X ray diffraction pattern of an alloy of Al and Mn and got a sharp pattern with clear five fold symmetry. The sharpness of the pattern meant that there had to be long range order, but the five fold symmetry meant that the solid could not be crystalline. Shechtman called the material a ``quasicrystal''.
One possible explanation (although this has still not been conclusively established) is that quasicrystals are three dimensional analogues of Penrose tilings (Scientific American, January 1977 -- Penrose tilings were known as a mathematical curiosity before quasicrystals were discovered). Penrose found that you could put together two (or more) different shapes in certain well defined ways so that they ``tiled'' the plane perfectly, but with a pattern that never repeated itself. Sure enough, some of these tilings do have five fold symmetries; and sure enough, there is perfect long range order (although no translational symmetry) so that the diffraction pattern from a Penrose lattice would be sharp.