Trying to convince internally that testing at an interactive prototype stage will be more effective at ridding usability issues than at a design stage. What are the benefits of testing early other than the fact it is more cost-effective?
Testing at wireframe stage can bring huge rewards and I would encourage it with any project.
The biggest and perhaps most obvious benefit being that it will quickly identify any key issues in your design, together with lesser issues that need only minimal adjustment. If not anything else, you could always think of it as a critical cost saving exercise (That's how I'd pitch it), if you get it right first time - even if it takes that little while longer - then you eradicate the need to spend hundreds of man hours / £'s on having a design built. Tested, then rebuilt and so on.
I also find that testing via wireframes allows for the exploration of multiple experiences, and indeed helps to identify and evolve those that prove to be a good fit. I can understand clients being a little apprehensive about letting a small group of users test an un-built, ghastly looking prototype, but there are people out there that are used to doing just that and will provide you with that oh so important feedback.
Approaching the best solution for an issue often is an iterative process. So, prototyping and testing at an early stage helps you in this process.
You often can prototype two or three alternative version and do a quick testing with colleagues, your mum or somebody from the street to find out which variant works best - and not which looks best.
Of course, design influences the perception of a page, a functionaliy etc. But it seldom really changes quality of the pure functionality.