An uninstall and reinstall will have no effect if the reason for the deletion of the avast icon is another security based program.
Navigate to your startup folder, C:\Documents and Settings\UserName\Start Menu\Programs\Startup once there, right click in the right hand window, from the menu, select New, Shortcut see image. From the new window click Browse and navigate to the C:\Program Files\Alwil Software\Avast4\ashDisp.exe file and select it and click OK, Next, name the shortcut and your done.