HeathCliff, we'll need more info to help you. First, did you uninstall Voice Search with Root Explorer, reboot, then download Voice Search from Market? Did it work perfectly? If you used another method, what did you do?
I'm assuming you've already followed my above instructions for uninstalling Google Search, so what was the outcome? Any errors? Any popups? Have you tried using terminal to uninstall? Is it possible that you already have the most recent version? To check that just go to Market, search for Google Search, and if it says "Install" then you don't have the most recent one, if it says something else then you do have the most recent one.
Finally, what handset/OS are you using (e.g. Droid 2.2, Magic 1.6, etc). Sorry if I've insulted your intelligence with over-explaining; I'd rather over-explain now then waste our time you being confused and me explaining later.