Had the very same issue. Found out that it has something to do with Java Runtime not being installed (or being installed multiple times which was not the case for me). Downloaded and installed latest JRE from Oracle, now Bonjour starts normally.
My system: Win7SP1 X64
Tried all you said and still did not work. Noticed itunes had an upgrade to fix the aiplay icon not showing. Fully uninstalled and re installed with latest version. Still get the same error when running itunes. "Bonjour not running. Start Bonjour in services to allow sharing etc" Try to start Bonjour and get error 1067
Uninstalled latest version and re installed 10.3.5 and everything works