Windows

Reinstall from the win98 disk by locating the system files to the recycle bin

Try deleting your info file for the recycle bin. Windows will create a new one at next startup. Enter these commands at a command prompt.
Cd recycler
attrib -h inf*
del info
Since it's a hidden file, you can find it by viewing hidden files in Windows Explorer.

Oh man, let Windows recover the recyle bin from scratch. So you can delete it, Windows will automatically recreate recycle bin the next time when you log in.
To delete recycle bin, you just do it from DOS:
At root of the drive type:

attrib -s -h Recycled
del recycled

Good luck

To easily fix it. Start by opening Windows Explorer. Make sure your Folder Options are set to show all files/show hidden files. Select the drive (ie. C:) and delete the Recycle bin entry. You'll be given and warning window saying ths is a System File. Click YES. Make sure you do this for each Partition. Then reboot the machine. Each partition's Recycle folder will be recreated at bootup.

just a little comment.. the recycle bins doesnt get created when booting up again.. but when deleting files. At least this was my case with win95/98/2000...

Deltree /y X:\Recycled where X is the drive letters on your computer.