Cyanide monolayers on Au{111} restructure from a hexagonal close-packed lattice to a mixed-orientation "ribbon" structure through thermal annealing. The new surface structure loses most of the observed surface features characterizing the initial as-adsorbed system with "ribbon" domain boundaries isolating rotationally offset surface regions where the orientation is guided by the underlying gold lattice. A blue shift to higher frequencies of the CN vibration to 2235 cm^-1 with respect to the as-adsorbed CN/Au{111} vibration at 2146 cm^-1 is observed. In addition, a new low-frequency mode is observed at 145 cm^-1, suggesting a chemical environment change similar to gold-cyanide crystallization. We discuss this new structure with respect to a mixed cyanide/isocyanide monolayer and propose a bonding scheme consisting of Au-CN and Au-NC bound molecules that are oriented normal to the Au{111} surface.