We present the discovery of five millisecond pulsars found in the mid-Galactic latitude portion of the High Time Resolution Universe (HTRU) survey. The pulsars have rotational periods from similar to 2.3 ms to similar to 7.5 ms, and all are in binary systems with orbital periods ranging from similar to 0.3 to similar to 150 d. In four of these systems, the most likely companion is a white dwarf, with minimum masses of similar to 0.2 M-circle dot. 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 make 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.