I have the same problem, that my 2932 contact, all the categories form outlook is missing.
To fix it : 1. Deletted first all contact in device, 2. Export the contact from outlook to CSV file., 3. Import account to webmail (your account gmail). 4. Syncronize your device to webmail.
Until now, i didn't fine to syncronize since upgrade to the lates KIES and FirmWare. There is no problem anymore with connecting (Which at first allways signed "Connecting......"), bu the contact still can not appear in kies even the syncronize was 100% succsess.
Oh.....my ....... my......., i think it's better use WP7 for hande syncronize data outlook.