Icons don't appear immediately for downloaded programs
This icon is shown to tell you that the program is potentially unsafe because you haven't opened it yet and it was downloaded from the Internet.

The first time you open the app, you'll see a security dialog that says, "App Name" is an application which was downloaded from the Internet. Are you sure you want to open it?"



Once you click Open on that dialog, the app will open and the icon will change to the app's normal icon.
You shouldn't need to restart or anything like that.