One possibility is that the old version was installed per user / Just Me, and the new version is being installed per machine / Everyone. Or, vice versa. Windows Installer does not "find" products installed in the other per user/machine state than how the setup is currently being installed.
Fortunately, in VS 2005 we added a two properties that can help. In the project properties is a property for the default install state... InstallAllUsers... and then on the Installation Folder dialog, a property where you can hide the UI to let the user change the mode.
Hope this helps.