Congrats on helping your client see the real issue was information architecture and not the UI - that's delivering true value through user testing. ;->
When I was supporting a consumer product, we set up bi-weekly user testing sessions for a mobile app that was in development. Here are a few of the key elements of that process that might be useful to you:
- We scheduled 5 users per day of testing (different people every week).
- The sessions were 30-45 minutes long and were very focused (didn't review the whole interface, just a particular feature or task flow).
- Often we used a prototype instead of a completed build so that we didn't use a lot of dev resources on code that was going to change. (Sometimes, when it was practical or necessary, we had a "live" product.)
- We required the product managers and developers/engineers to attend the day of testing, so they could see first hand where customers were struggling. I gave them instructions on how to observe and what to listen for and told them to take notes that we would review at the end of the day.
- After the 5th user finished, we gathered for a group debrief and created a list of all the things we heard/observed. Then we prioritized the list and picked the top 3-5 things that needed to change for next time.
- Developers/engineers went off for 2 weeks (the team's sprint length, at the time) and implemented what they could of the 3-5 key takeaways and I had that time to tweak the script for the next round of testing.
Many of the developers had never seen an actual user test, just consumed reports that summarized the findings. It was much more effective for them to watch, in person, because they really felt the users' pain. ("I can't believe they don't see the blue button - it's right there!!!" But they couldn't deny what they were seeing with their own eyes.) . Sometimes, after the 3 morning sessions, the developers would have already tweaked the UI and wanted me to put the updated design in front of the afternoon participants to see if it addressed the issue. Even if they didn't have the solution coded by the end of the day, they had a good idea of what they wanted to change for next time and were excited to make the improvements and collect more feedback.
I hope this helps answer your question. Feel free to reach out with questions, if you have any.