We have embarked on a survey for pulsars and fast transients using the 13-beam Multibeam receiver on the Parkes radio telescope. Installation of a digital backend allows us to record 400 MHz of bandwidth for each beam, split into 1024 channels and sampled every 64 us. Limits of the receiver package restrict us to a 340 MHz observing band centred at 1352 MHz. The factor of eight improvement in frequency resolution over previous multibeam surveys allows us to probe deeper into the Galactic plane for short duration signals such as the pulses from millisecond pulsars. We plan to survey the entire southern sky in 42641 pointings, split into low, mid and high Galactic latitude regions, with integration times of 4200, 540 and 270 s respectively. Simulations suggest that we will discover 400 pulsars, of which 75 will be millisecond pulsars. With ~30% of the mid-latitude survey complete, we have re-detected 223 previously known pulsars and discovered 27 pulsars, 5 of which are millisecond pulsars. The newly discovered millisecond pulsars tend to have larger dispersion measures than those discovered in previous surveys, as expected from the improved time and frequency resolution of our instrument. ; Comment: Updated author list. 10 pages, 7 figures. For publication in MNRAS