I would guess that Gamestop doesn't even flash a new firmware on thier refurbs. Question: Does is still have the Sony Warranty sticker on the side? If so, your refurb was only tested to make sure it works properly and probably cleaned off.
Take it back to Gamestop. Find out which one of the guys is the "PS3 guy". Explain your situation. As long as he isn't some flaming PS3 purist, he will sympathize with your plight and let you find one that has 3.55 or lower. I B.S. with the guy at my Gamestop all the time about hacks/CFW. If they only have one other PS3, find a Gamestop that gets more traffic and thus, has more PS3s.