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, omegadot = 0.28 +/- 0.01 deg/yr 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 Msun and 1.38 Msun, making it likely to be another neutron star. We also place a firm upper limit on the pulsar mass of 1.38 Msun. The expected coalescence time due to gravitational-wave emission is long (~60 Gyr) and this system will not significantly impact upon calculations of merger rates that are relevant to upcoming instruments such as LIGO.