I ran into this issue of Samsung Kies not detecting Galaxy S for Bluetooth connections. Samsung Kies is just displaying Windows Mobile and Symbian as the choices! I never thought Samsung also had Symbian phones in their range:
This is happening on a Windows 7, 64-bit Home Premium and the Galaxy S is currently on Android 2.1, Eclairs.
On a slightly different note, I also feel that Samsung Kies is not the best of the Mobile-PC Sync software I have seen. Even the Motorola Phone tools released for V3i in 2005/2006 had more features.