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.
Test the usability not the design and perception of what you developed. Evaluate your solution quickly without involving a designer - I guess efficiency would be the main argument.
Of course, design influences the perception of a page, a functionaliy etc. But it seldom really changes quality of the pure functionality.
Interaction is not the only aspect of usability testing. Visual design and motion design lead to discoverability, and findability as well as assisting with information hirerarchy and learnability. As a result the answer is:
Yes in that testing before any visual design happens is extremely beneficial and can represent a large cost savings, however, the visual and motion design can make or break the design in the ways mentioned above, so you need to test when these are in place as well. Banner blindness is a classic example of a way something might work fine in a wireframe but would fail later.