We report the discovery of a new binary pulsar , PSR J1829+2456 , found during a mid-latitude drift-scan survey with the Arecibo telescope . Our initial timing observations show the 41-ms pulsar to be in a 28-hr , slightly eccentric , binary orbit . The advance of periastron \dot { \omega } = 0.28 \pm 0.01 deg yr ^ { -1 } is derived from our timing observations spanning 200 days . Assuming that the advance of periastron is purely relativistic and a reasonable range of neutron star masses for PSR J1829+2456 we constrain the companion mass to be between 1.22 M _ { \odot } and 1.38 M _ { \odot } , making it likely to be another neutron star . We also place a firm upper limit on the pulsar mass of 1.38 M _ { \odot } . The expected coalescence time due to gravitational-wave emission is long ( \sim 60 Gyr ) and this system will not significantly impact upon calculations of merger rates that are relevant to upcoming instruments such as LIGO .