I personally wouldn't recommend a used DSLR camera. They need more daily maintence then a regular 35mm SLR camera. I could see buying a used 35mm SLR because as long as the shutter works correctly, everything should be okay. Clean it up, once over it, and load it up for some testing shots. The difference is that image sensor in digital cameras. If they're not kept clean correctly, you could wind up with crap that never comes off, or worse, a toasted image sensor.
I was gonna ask/say what spoofskate said regarding what lenses he already has, but it seems like he only had one, and it's broken. So I'd figure out which camera he likes best and buy the kit. Kit lenses aren't crap as one person said, they may not be $400 dollar HQ lenses, but they're pleanty good enough to start with and if he wants more flexibility he can buy another lens. Hence the nice part about SLR.. If you choose Canon or Nikon, you have an endless supply of lenses and such from all manner of makers. Personally, I choose a Sigma camera as I liked it best and it takes wonderful photos.
So basically, figure out what he likes best and surprise him with that.. =)