We report an extensive investigation of magnetic vortex lattice (VL) structures in single crystals of pure niobium with the magnetic field applied parallel to a fourfold symmetry axis, so as to induce frustration between the cubic crystal symmetry and hexagonal VL coordination expected in an isotropic situation. We observe new VL structures and phase transitions; all the VL phases observed (including those with an exactly square unit cell) spontaneously break some crystal symmetry. One phase even has the lowest possible symmetry of a two-dimensional Bravais lattice. This is quite unlike the situation in high-Tc or borocarbide superconductors, where VL structures orient along particular directions of high crystal symmetry. The causes of this behavior are discussed.