I had the same problem more than once. The most frustrating point was after a revert to stock 2.3.6 after stock 4.0.3 and, with full wipe & clear cache, sometimes I could connect, sometimes I couldn't. Somehow it managed to connect so I was happy and left it as it was.
A few minutes ago I wasn't able to connect to Kies without doing anything in particular (I have GO Launcher, by the way), thus I found myself on this thread
How I managed to make it work?
After (unsuccessfully) trying to connect it over cable, I tried connecting over WiFi and I got a message informing me that Kies for USB is already opened (I don't remember the actual message) and I kept receiving this message even after "Clear memory".
So, I just restarted the phone (I long pressed the power button until the screen turned off and on, with the S logo) and it worked like a charm after that!
Hopefully this will work for you too, guys.
Edit: Sorry for bumping this old thread, I misread the year...