I have been pulling my hair out over this issue and HOORAH just got my Galaxy S2 to connect to Kies!
After trying the tips in this thread and other forums I ended up by simply taking out the SD card AND the sim. After powering down of course. Restarted the phone without the SD and SIM cards, started Kies, connected using the usb cable and bingo it recognised the phone!!
I am now currently backing up in preperation to upgrade to ICS.
Hope this is of help to anybody else having this problem.