Issues with Windows Installer and Recycle Bin

For the last couple months, I've been having issues on my laptop (which is running the wonderful Windows Vista). Any time I try to install a program that uses the Windows Installer, the install freezes, and ultimately freezes the entire computer. This also happens when doing a Windows Update (presumably because it uses the Windows Installer).

I've also recently had issues when deleting things. The window comes up that shows it's being deleted, the progress bar starts to move and then it simply hangs. The only way to clear this window is to stop the Explorer process. This doesn't cause my computer to freeze though, and restarting explorer.exe makes everything ok (until I want to delete something else). This also happens when I try to empty the recycle bin.

What could cause each of these issues, and what (besides reinstalling Windows or upgrading to 7) can I do to fix them?

 

Actually, I think it's an explorer related problem... my notification icons like network and battery, don't change when they're supposed to (battery showing it's plugged in, network showing the globe, etc).