While I generally side with you that original work implies that you performed the work from scratch, I must ask a few questions:
Did the client approach you about this or did you pitch it to the client?
If you are the one that pitched the idea then the client trusted you to truly wow them since they are likely paying a premium for these original emoticons. If they are left with the feeling that they were better off getting something off the web for cheaper and with less time consumed then I can understand their frustration.
What does the client do as a business? Could this be the next WhatsApp?
Maybe they were expecting a truly amazing icon set that they can put their brand behind. If they are just running some forum then they can certainly use some stock off the web and be done with it. If they were banking on an awe-inspiring emoticon set that would differentiate them in their business-space then I can certainly see why paying a premium for "more of the same" (in their eyes) is somewhat of a let-down. On the flip-side, if they didn't pay a premium then it is somewhat rude to expect a 100% stellar product.
I just want to make it clear that I am not critiquing you nor the hours that you've certainly put into your work but these could be valid points to consider during your next contact with the client.
Update
After seeing the full text of the email which your client sent and reading the comments throughout this post, I would like to offer the following reply:
Hello Mr/Mrs/Ms. Client,
I would like to assure you that the work I submitted to you is 100% original in terms of me performing the design process from start to finish. Yes, you are correct that there are many emoticons on the market and at first glance they all look similar. I made sure that the emoticons submitted to you were differentiated.
Any steps that we can take to avoid legal issues are steps which I would like to take with you. As of right now I can offer you all of my original sketches and mock-ups which led to the design of the final product. I would like to also offer a Certificate of Authenticity which guarantees that the work I performed for you is 100% original and will not be resold in any way. Per our contract, your company will own full rights to these emoticons.
Please let me know if your company would like to take any additional steps in securing the emoticon's authenticity.
Many of the statements made above take a lot of assumptions into consideration about your contract and what you are willing to do so definitely modify it to fit your situation.
It sounds like the client hired you so that they can avoid paying royalties for using someone else's emoticons. They also want to avoid the possibility of being sued. If they do get sued then they need to be thoroughly certain that they can stand their ground and did not rip off someone else's established work.
My primary goal was to be as objective as possible and focus on the fact that they are worried about legal issues and this has absolutely nothing to do with being displeased with the design. I like your emoticons by the way :-)