I opened a support case with Symantec regarding this. The resolution was to create an exception in Application Control to allow C:\Windows\System32\msiexec.exe. But allowing this basically allows many other programs to be installed. Ask, Bing, Yahoo toolbars were all able to install. This basically makes the rule - Prevent registration of new Toolbars ineffective.
I was told to enable the exception when I want to install Adobe on a client. We could use that as a work around however those clients that already have Adobe installed are unable to update the software as it blocks all updates to Acrobat as well.
I am kind of suprised that no one else has had this issue in the past.