We're running a project and we come to conclusion that the approach used in the project to handle the business issue is not performing as expected. We're changing the scope of the project to meet the business requirements. Should a change request be raised? Who should write it, if needed?
A change request or contract modification is certainly in order in this scenario. I'm assuming that the running of the project is part of a contract, so in almost all cases a significant change in scope would require the mod. If the contract is time and materials this may not be the case, but as a Project Manager it is important that you keep your customer informed, and in this case a new scope would be an important thing to discuss with them.
As for who writes up the modification, it would depend some, but traditionally this is the responsibility of you the contractor. You may need or want input from the customer so that you both know what the impact and expected outcome of the case of scope entails, but ultimately since you have to accept the new work it's on you to write the mod.
In the extreme, this scenario may be grounds for vacating the existing contract completely and starting with a new one that covers the specific appropriate business need.