Signed Exe is being blocked by Vista

I have a digitally signed program that is being blocked when run on
a
particular Vista Home Premium machine. The same program runs fine on
other machines, it's just this one machine. Each time the user tries
to run the program they get the "Open File - Security Warning"
message
dialog. The Publisher is listed (so it's not unknown).

The problem us that because Vista is seeing the program as "bad", it
runs in a lower priv level than is needed to run the program (i.e.
access to reg keys and profile information) and the program does not
work,


How do I get this program off the "bad list", or get the Publisher
back on the trusted list?