It is supposed to be done without the GPS connected contrary to the instructions. If it still doesn't work, contact Garmin by phone or email. We know they have dealt with this problem before from others on the site and are generally very helpful.
EDIT. I am assuming from your description you are using the version of Mobile PC that comes with a GPS (USB 20x or BT 10x). The software only version does not support map upgrades.
Terry