I eventually got Gingerbread on my Fascinate, but it was quite a chore. It was doing the same thing. Stopped saying "I need an update"
I eventually figured out that the drivers required for Kies to work with my phone, didn't install properly when I first plugged the USB from my phone to my PC. I didn't go into Device Manager and verify if they were ever installed, or if they were, but weren't working/active, though I suppose you could do that.
After a few reboots of both the phone and the PC (everytime they failed to connect), I noticed that I got the confirmation "Drivers Installed" window, with a list of about 8-10 drivers (with green check marks beside them) that installed via USB from the phone, onto the PC.
Once this happened, everything went smooth.
Like I said, no real method, I just rebooted the PC, then the phone. Once both up and running, open Kies on my PC, then plug in the phone. It took several tries, but it eventually worked, and now that I have Gingerbread on the phone, it connects everytime to Kies, and quickly.
Sorry no more help, but after about 6 or 7 tries it worked. Hopefully it's quicker for you.