That's an interesting point. It's illegal for Google to store my personal data without my consent (I am a EU citizen).
I suppose they can store other people's address books because it's the "legitimate interest of a third party". I'm pretty sure they can't then use that data (my phone number) for any purposes beyond the third party interest - which means they can't use it for advertising, or to link to any user profiles they may have on me. Basically, they can store address book data, but they can't look at it for their own purposes.
That obviously doesn't apply to US persons, who have no data protection right - hence the horror stories of "friend suggestions" that have obviously come through service providers peeking at address books. I wonder how they can practically filter out EU citizens from that - I suppose it's easy to spot an EU phone number.
(Just to head off the inevitable "Google doesn't care about EU law" scoffing... I think you'll find they do. They only get to export Europeans' personal data to the US because they've agreed to uphold the Safe Harbour principles. If they abuse that privilege, they'll have to do a lot of expensive re-engineering.)