A refurb performed by Canon or Nikon means the camera is in theory literally good as new. Check the warranty on refurbs. Some have a more limited warranty; others carry the full term regular manufacturer's warranty. Used gear will vary more in condition, so a refurb is IMO safer and at the very least it will be more consistent (they will all be similar in quality, condition, etc.).
EDIT: Also, I could swear the D5000 has a more conventional, less hold-your-hand menu system than the D3000. They will both come with the same kit lens but it is generally quite good IMO (the 18-55 or 18-55 VR depending on the particular kit).