I used to have the same issue. Thankfully Thunderbird, which I switched to, has a bidirectional contact sync plugin for google contacts.

FWIW the last time I tried KMail with GMail, there were some issues with how the folder-to-tag mapping worked. This ended up with me needing to untag a lot of stuff manually in my GMail. But since this was over a year and a half back, I wont really go by this. Things could well be better now