First, set aside a half hour at least. That's how long it took my customer service person, and it wasn't her fault but the call center she had to negotiate with.
I just did this, and all you need is the phone number you gave at the time of the warranty. I would also suggest that you have an error that can be clearly demonstrated on the spot (eg, my one red light was immediately apparent), because in my case they insisted on checking it out. I don't care which error, but make it something they can't ignore, I have a feeling there's a real YMMV as a result of how closely they are scrutinizing xbox returns.
You don't need the box or documentation, they'll just check the serial number on the xbox. You can keep your HD, just take out the new one and return it to them on the spot (I had to explain that the old hd I had at home would, in fact, work just fine with a "new" elite). Bring back as much crap as you can find, headset, controller, video cable, whatever.
Also, depending on which version you have, you may be up for a gift card refund as a result of xbox price drops. They did it automatically so I don't think there's any way to screw you out of it.
When I returned GHWT as defective, the process was much quicker with no need for testing (granted, that was under "defective when purchased"). I expect the nature of the xbox return fiasco makes it a much more delicate issue.