I am on my third brand new DX. The first had a bad screen (banding and flickering). The second had a serious rebooting issue. The third has been working fine since receipt.
I have gone through Verizon's Warranty department, using the Warranty phone number that is preloaded on the phone. I haven't talked to anyone else, and I didn't go to the store where I bought it. The reps on the phone have clearly stated that within 30 days, you are ENTITLED to a brand new replacement. You should NOT have to pay a restocking fee...you aren't returning it because you changed your mind. You are returning it under warranty. Be firm in your stand and get what you paid for.
BTW - when mine started rebooting, it was about two weeks into ownership, and I was getting ready to go out of the country for several weeks. I called the Warranty number and asked them to make a note in my account stating I was having rebooting issues and asked if they could extend my 30 day window for Worry Free Warranty Exchange. I said I'd give the phone another couple weeks to see if it cleared up, and I was hoping 2.2 would be out and magically fix the issue. Well, the issue persisted. When I called Verizon Warranty dept (outside the 30 day window), they confirmed that the issue was noted in my account and I was still able to get a replacement under the Worry-Free Exchange program. Great service for me so far!