It may be that are using a 3rd party application such as Norton and you have the "Protect recycle Bin" feature activated. If you are not using such a utility, then you can use a simple registry fix below to repair/replace the recycle bin in Windows XP:
http://www.5starsupport.com/download/replbin.reg