Redrawing something means you have created derivative work, not original work. (PDF from copyright.gov) Merely "redrawing" something does not, in most instances, grant you an unencumbered copyright.
In addition, there is no such thing as "change it by x amount and it's okay". If the original image can be discerned from the copy in any way, it maybe infringement as well.
If a company is informing you that you need to purchase rights, that would indicate that they feel you are infringing upon their copyright (or the copyright of the original artist). How and to what depth or expense you are willing to go to in order to fight their perception, is up to you.
I am not an attorney and no part of this answer should be seen as legal advice.
The reality is they feel you are infringing, you feel you aren't. That's a legal battle. My opinion won't mean anything. Neither will the opinion of anyone else. Only a judge can definitively determine who may be correct.
You have 3 choices....
- Acquiesce to their demands
- Hire legal council to immediately inform them of your disagreement
- Ignore them and deal with any possible repercussions should they wish to pursue the matter further - i.e. The need for legal council at that time, and possibly paying penalties, your legal fees, etc - if you were to lose a judgement