My girlfriend had the same problem Just go to control panel -> appearance & themes -> click the left hand side that says desktop items -> click the recycle bin check box, it should now reappear on your desktop.
Edit: ohh didnt notice, that you already solved it
Just go to control panel -> appearance & themes -> click the left hand side that says desktop items -> click the recycle bin check box, it should now reappear on your desktop.