I had this problem too in FF3 (3.6.17 but I'm pretty sure it started with an earlier version). Deleting the icon cache didn't work, and while I've come across solutions that involve changing the registry, I didn't want to do that myself. However, I found that it was solved by uninstalling and reinstalling, as follows:
First, take a backup of everything using MozBackup. Then uninstall FF3, selecting the option to completely remove personal settings. Then reinstall FF3, but without creating a new profile. Close it, and restore the old profile with MozBackup. After this the file icons were as they used to be.
One thing to bear in mind: the profile in the new installation has a different name (the seemingly random sequence of letters and/or numbers) from the old one, so if you have any backup programs etc which refer to it you might need to change their settings.
After this I actually upgraded immediately to FF4, and the icons stayed as they should be. It might have been possible to simply install v.4 without putting v.3 on again, but in my case, one of my add-ons (a viewer for the family history site Ancestry) apparently can't be installed from v.4, but will continue to work if it was in v.3 which is then upgraded.
In case anyone is wondering, I had first tried upgrading FF3 with wrong icons directly to FF4, but this didn't solve the problem. It was only the uninstall/reinstall that worked.
Hope this helps others who don't like changing the registry!