This isn't actually an issue with digital certificates (despite the evidence that might lead one to believe otherwise). The problem is that Vista doesn't allow apps that require admin elevation to run at startup.
We weren't originally planning on working around this, seeing as MS declares it to be "by design" and "intended behavior."
However, thanks to a host of people asking us to re-think that decision, we've developed a version of iReboot that bypasses all the UAC prompts and can run at startup without any nags or problems.
I think Vista simply remembers the fact that you had configured the file with name "iReboot.exe" in that path to be run as an administrator and was (incorrectly) applying that option to the new version as well... out of my hands, unfortunately.
Installing it as administrator shouldn't be an issue - you'd have been asked for UAC elevation to admin rights anyway if you hadn't, because the setup needs admin privileges.