We present the discovery of 5 millisecond pulsars found in the mid-Galactic latitude portion of the High Time Resolution Universe (HTRU) Survey. The pulsars have rotational periods from ~2.3 to ~7.5 ms, and all are in binary systems with orbital periods ranging from ~0.3 to ~150 d. In four of these systems, the most likely companion is a white dwarf, with minimum masses of ~0.2 Solar Masses. The other pulsar, J1731-1847, has a very low mass companion and exhibits eclipses, and is thus a member of the black widow class of pulsar binaries. These eclipses have been observed in bands centred near frequencies of 700, 1400 and 3000 MHz, from which measurements have been made of the electron density in the eclipse region. These measurements have been used to examine some possible eclipse mechanisms. The eclipse and other properties of this source are used to perform a comparison with the other known eclipsing and black widow pulsars. These new discoveries occupy a short-period and high-dispersion measure (DM) region of parameter space, which we demonstrate is a direct consequence of the high time and frequency resolution of the HTRU survey. The large implied distances to our new discoveries makes observation of their companions unlikely with both current optical telescopes and the Fermi Gamma-ray Space Telescope. The extremely circular orbits make any advance of periastron measurements highly unlikely. No relativistic Shapiro delays are obvious in any of the systems, although the low flux densities would make their detection difficult unless the orbits were fortuitously edge-on.