Remind your client that Google is not a benevolent entity, they are a Wall St listed company who must earn increasing amounts of profit for their shareholders and that, increasingly, they are needing to send traffic with buy intent to locations other than the small websites it has been for years which may or may not impact your client's site.
Perhaps your site was deemed redundant in Google search results because Google now shows essentially what you did in their own sidebar? Only Google knows for sure.
The bottom line is that there is no fault in your situation, only change. Google is not just a search engine anymore.