Solution: Create a shortcut to the Premiere Pro executable file, rename the shortcut to Premiere, and move the shortcut to C:\Program Files\Common Files\Adobe\dynamiclink.
As dumb as it may sound, it worked! And I didn’t had to uninstall or reinstall nothing. I kept both my CS3 and CS4.