It most certainly does not make sense to cancel the order for someone that doesn't want to cancel.
I agree it is inconvenient to ask a customer to cancel and replace an order (the support rep could be doing that transparently for the customer), but it seems it was a very unusual case (theft or loss of the package) so it is reasonable to expect a somewhat unusual process to resolve the situation.
http://www.google.com/chat/voice/
I've personally learned the hard reality that most people currently alive cannot use email correctly and therefore demand that everyone they do business with provide phone support. Because of this, the path of least resistance is to just be like them and get used to calling when you need something resolved. (And the reality is, it's faster for the people at the other end, which is why it persists.)