For me it was actually an encryption issue.  I use file encryption and the punkbuster files were encrypted using my software and that made their certificate invalid as they were under my own personal certificate.  I did stuff like uninstalling punkbuster via the PB utility, then manually removing any trace of it from the registry and reinstalling via the same utility and even running PBSetup after that.  Worst case scenario uninstall everything and reinstall, but thats usually not needed.