I just downloaded and ran the Contact Transfer app, it seems to have worked. But where online do I find the contacts that were backed up? Where is the Cloud?
Login to the My Verizon website (verizonwireless.com). Hover your cursor over the "My Verizon" tab, then in the "My Device" column you will see "Manage & Store Media". Click that link.
For some reason, Verizon had not put the word "cloud" anywhere in this path as of May 25, 2013.