I tried going through Verizon's support, and then Samsung's support. Neither place was able to figure out why everything else was working properly but the Market wouldn't.
I then talked to the sales rep I bought the phone from. He had me return it to the Verizon store, where I was given a replacement phone with the assurance that the 2.2.2 update on the Samsung site would work. In fact, the in-store rep assured me confidently that he had already used it to update several phones.
With that assurance, plus the promise that I could return it if it gave me any trouble, I tried updating the second Gem, which of course, did not work any better than the first one.
I returned that one also. This time, a different sales rep waited on me and advised me not to try to update the Gem to Android to 2.2.2. I complained that I was told the phone had 2.2 on it when it was sold to me, and that I was extremely dissatisfied with the misleading information. After a few minutes of conversation, I ended up getting an LG Vortex (with 2.2) for $50 with a $50 rebate.
Bottom line - at this time, the Samsung Gem cannot be updated to Android 2.2 and has not as yet been rooted successfully. If you are within your 14 day grace period and not happy, return it for something more up-to-date.