I've run in to this type of problem before and have a solution that has never failed me. I simply tell the clerk that they can have the box and packing materials the replacement unit comes in since I don't need them.
Apparently the box has a code on it that corresponds with the phone. They ended up using the code on the inside of my phone to make the exchange. I checked the new phone and compared it with the new box and the code is exactly the same. Why they gave me such grief is beyond me.