A multibeam survey for pulsars using the Parkes radio-telescope has discovered a 22-millisecond pulsar in a nearby 2.4-hour eccentric binary system. Subsequent observations have also revealed that its companion is a 2.7-second radio pulsar, for the first time confirming the neutron-star nature of the companions in such systems. The discovery of this system has significant implications for the expected rate of coalescence of double-neutron-star systems which might be detected by gravitational wave detectors. Furthermore, the presence of the second detectable pulsar also promises to make this an important test-bed for new rigorous tests of strong-field gravity and general relativity and for probing the magnetospheres of radio pulsars.