Agile - Getting Users involved early.

Let me quote an example from one of my projects where I was a consultant. This was a project for Government and they hired a consultant to write RFP which contained requirements in as much detail possible. The project implementation contract comprised of commissioning both hardware and software required. Hardware part was straightforward and most of the items had to be just procured and configured. The only issue there was delay in issuing Purchase order. At times we were forced to select a particular piece of hardware as for the quoted price there was no choice available.
Now coming to software part. The Govt. Office was doing most of the work manually till date without using software. They wanted a software which is best as per industry standards. During  requirements phase things seemed easy for the client.  When we as vendorsstarting builing the software they had lot of questions and clarifications which were answered by client very lightly without going into details. 9 months later when the software was delivered for UAT, Client was not happy at all with the software. 
How can this be possible ? . We selected best in the class software, read the requirements well, clarified at every stage with client, and when we deliver for UAT , client is unwilling to sign-off. In fact they are not even able to test all parts of the software.
Here there was a strange issue, which our company did not envision before. The solution was over-Engineered for the client. They did not have required data for all fields, In absence of data all functionality would not work as desired in UAT. There were other issues with User interface also. Client officials were used to simple paper based forms and the new software screens seemed too complex for them. 
So how could we possibly have avoided this situation ?
Agile methodology could have done this, instead of showing the end product after 9 months, if we had split this into 9 sprints of 1 month each, with each sprint delivering working code into production, we could have got early feedback from the client, made corrections in future sprints. Considering client was not using any software their deep involvement in Agile process would have got them upto speed with using the software and SDLC.  Not only that the bite sized releases in production would have taken care of Organisational change management issues and resisitance involved in moving from manual to software based system. 
You must have read it many times in the past that getting users involved as early as possible is a best practice. Delivering software is not a magic trick where after 1 year you deliver and the client goes Ooolalaa over the software. Most of the times, the answer is, "this is not what I really wanted, I was hoping...."
The cost of rework and changes in above project had cost us a fortune and we could not make any profit in this project. Changes have to go through the rigorous Change management process and often there is a conflict with client on whether its a change or part of original requirement. 
What makes sense for an IT company and Programming team may not make any sense for Client or their Business SMEs. They look at things from very different perpective and getting them work in agile model will get them involved early and avoid any surprizes during Acceptance testing or go-live. 
In our case the client was very upset with the vendor company and we lost reputation and future business from the same client department. These days clients are well aware of technology and UI,  as they may have seen some great software on their smart phones and expect the same from their vendors.  Government officials generally make commitments to their ministers and even the citizens and announcing a delay is usually very difficult and can even take a political angle. You will have to spend time communicating with media and giving explainations to other stakeholders. 
So if you are doing a project analyze the scenario and evaluate if Agile methodology is required, else you will be headed for big time failure.