You need to rebuild the launch services database. There's several utilities that can do it, or you can just run this from the command line:
/System/Library/Frameworks/CoreServices.framework/Versions/A/Frameworks/LaunchServices.framework/Versions/A/Support/lsregister -kill -r -domain local -domain system -domain user
Restart Finder afterward (or logout & login or reboot) if you don't see the changes immediately.
If you're not on 10.6 you'll have to google to find where lsregister is - I can't recall offhand.