OK, true to form as soon as you post for help on a forum, you fix it.
Here's what had happened, although the installer had installed it into the correct folder and added the registry item.
The click once trust behavior in registry was all set to disabled and my certificate, even though I installed it into trusted root, just wasn't working.
I used the setting for How to: Configure the ClickOnce trust prompt behavior
I can't link to it ironically I'm not trusted yet, but searching for that will find it.
Also when I got another user to check, who was having the same problem, they did not have those registry settings at all.
Double clicking the vsto file installed it correctly and it's now working. So it seems that the installer was in fact not installing the vsto correctly, no idea why that would be, if anyone knows, please let me know.