Educate the customer. I wish I'm not one of your customer ;)
Seriously, I understand your are in trouble, and you think the problem is the customer. Maybe it is, but it doesn't matter. Changing your customers is really hard, while changing the way your work with them is lot more easier.
The problem is that most customers are not aware of all implications of software development and you are not aware of their business in details.
Just one little thing:
changes are not a problem in any time of the project
"No matter how far you have gone on a wrong road, turn back." Turkish Proverb
I love that proverb, so when I can use it, I'm happy. Thanks for the opportunity ;)
Here are a couple of solutions:
You must provide the customer with the possibility to change his mind, because this will help him getting the right software that really fits its needs. He will eventually get more ideas while you are developing it.
Your are in a fixed price contract, so I guess you had to gather requirements, estimate them and put a price on each?
If you have to build a new thing, use the same process: you amend the fixed price contract with the extra requirements. Accept to remove requirements that will be useless (of you have not built them already of course).
Another approach would be to finish what has been negociated (less useless and not developed requirements) as version 1, and negociate a version 2 with its new ideas.
The second solution would be to create iteration in the development like in Scrum. I've no experience with this yet in fixed price project (because I don't do fixed projects anymore), so I don't know if it works or not. I seriously have lot of doubts Scrum (or Agile) is the solution to all software development projects, but maybe some of the practices described will help you.