This annoys me more than anything - not just google, but for a large and growing number of sites. They completely ignore your browser settings and select language based on IP address. I installed the google international search plugin from mycroft which has solved my problem with google - but still suffer the myriad of other sites that ignore my browser's config.
I think in the past we saw a lot of people with their Accept-Language header set wrong, which is why we haven't used it. But we've been having a good discussion internally about the "my language won't stick" issues raised on this thread.
How practical would it be to initially trust Accept-Language but also prominently display a link to change to the language detected through IP geolocation (with an easy way to hide/decline the link)?