How do I change photo associated with client's website on Google search results page?

Hi,

When my client enters his company name followed by his company’s location into (German) Google, he sees a box on the right hand side of the results page listing his company name, address and contact details.
This is good, but above this information there is also a photo which Google seems to have pulled at random from his site.

He has asked me to change this photo, but I have no idea how.

Although I don’t want to mention my client’s name here, you can see an example of what I mean by entering “Harrods London” into google.com
Link

So far, I have tried going to his Google Business Places account (http://www.google.de/business/placesforbusiness/) and uploading a different photo.
That was two weeks ago, but unfortunately the old photo is still showing.

I would be grateful for any help or advice.

Your example site looks like it may be pulling the image from a Google Plus account. Have you tried setting pictures in google plus account associated with that same Google account?

Hi,

Thanks for your reply.
I didn’t actually create a Google Plus account for this client, just a “normal” Google account which I used to set up Analytics and Google Places.
I’m presuming that some steps would be necessary on my part to create a Google Plus account. Please tell me if I am wrong.

The photo is definitely from my client’s web site, so what could I be missing?
My client is desperate to change it, so I would be grateful for any further advice.