If that is what they want, then I'd try to do it for them. At some point you need to let them come to the conclusion that it can't be done if that is the case and try to work with them on how to do it.
Can you create a lookup table that would determine the correct category in your database based on the category passed in the spreadsheet?
I'd ask them how they would figure out the correct category based on the information provided in the excel spreadsheet. Then you can probably mimic that logic and have it done automatically, and then bill them for the extra time it takes to do.
If it is actually impossible then you should be able to get them to see that by trying to find a solution with them and determining together that you really don't have enough information to make it happen.
I generally tell people nothing is impossible provided that we have enough information to figure out the answer and they have the budget to pay for the amount of work that needs to be done. I tell people "Don't ask if it is possible. Ask how much it would cost, because anything is possible". Then figure out a way that it would be possible and tell them how much it would cost.