Vista - Microsoft Games won't run

I have a client who until recently was able to run MS Games (Freecell, etc)
For some unknown reason he can now only run these games by right clicking
and running as Administrator.
To try and run the games in the normal manner he gets a message "The
publisher could not be verified" Strange when it's a Microsoft program...
And even when he clicks yes to the message "Are you sure you want to run this
software.." he still is unable to get the program to run.
Some info regarding the system. He is running Vista Home. with all the
windows updates. No new software has been installed and the system has been
checked for viruses etc. The user was created as an Administrator and he is
the only person using this computer.

Can anyone offer some advise. Desperate to get this fixed for him before
Christmas.