To fix this issue in Windows Vista, follow these steps:
1. Click Start, and then click Control Panel.
2. Click Appearance and Personalization, click Personalization, and then click Change desktop icons.
3. Click to select the Recycle Bin check box, and then click OK.
If that doesn't restore it go to:
How do I make the Recycle Bin appear on my desktop in Windows Vista or in Windows XP? and read the section on the registry hack to solve the problem/