Same thing...they didn't give a correct answer on this issue
We tried everything, re-added in circles in google+, rejoined google play, cleared cache. When I joined the game, my friend already had an account and somehow he had me in friends, but later he rejoined google and I disappeared too. So we don't any connections now, at least one of us.
I have last idea (not sure if this will work) how we can appear in the list of friends - visit our cities through Global Trade, but we wasted a lot of time just seeking in HQ without any results (it is hard because we are not low leveled)
