I think it will be partly because your client is looking for instant results, when SEO takes time to develop. I also don’t think people realise that it takes constant upkeep, and it’s not ‘my SEO is done, now what’ kinda thing.
Here is an article you can show them that explains how long it really takes:
also, there are so many things you can do to improve - I’ve been reading every blog I can to learn how other people are doing it. Here are some links you may find interesting:
http://backlinko.com/seo-techniques
http://neilpatel.com/2015/05/19/no-link-building-strategy-is-complete-without-these-12-tactics/
I would avoid working for free as it devalues what you have already done - show your client how using SEO and Marketing together (on Facebook, Twitter, etc) can get those visitors across.