The fix is quite simple; all you need to do is delete the System's Launch Services' database and restart your computer (logging out, then back in again should also work). This little trick will also clear up any duplicates you might have in the “Open with” contextual menu, and will reset the security prompt you see every time you launch an application for the first time.
So how do you delete Launch Services' database? Well, there are two options:
1) Using TerminalIf you have no qualms about using the Terminal app, simply copy and paste the following to the command line and hit enter:
2) Using the FinderIf you're a bit wary of using Terminal, simply open a new Finder window, navigate to /System/Library/Frameworks/CoreServices.framework/Frameworks/LaunchServices.framework/Support/ and delete the lsregister file.
That's it, folks!Whichever option you preferred, you just need to restart, and enjoy your polished Dock.
Dominic, in the comments, point out that you should empty the trash to complete the job.
If you have any doubts about any of the steps above, leave me a comment and I'll try to help you.