Error - You Do Not Have Sufficient Access To Uninstall XXXX

I have developed a Visual Basic application but this issue happens regardless of the programming language used to make the app. The application consists of a single EXE file. Now I am trying to add install/uninstall capabilities to it without using external setup packagers like InstallShield or whatnot..

For example I have programmed the command-line switch "/install" to add the necessary registry key values under HKEY_CURRENT_USERSoftwareMicrosoftWindowsCurrentVersionUninstall This has worked flawlessly. Now my application appears in the "Programs and Features" list along with all other installed programs from my computer. Now when I click the "Uninstall/Change" button it is supposed to execute the contents of the "UninstallString" key which is calling my application with the "/uninstall" switch. This in turn will delete itself and remove the entry from the registry.

The problem is that when I click the "Uninstall/Change" button I get an error message saying that I do not have sufficient access to uninstall my app even though I am logged on as an administrator.It is worth mentioning that if I right click on the executable file, select "Properties" and check the "Run as administrator" option then the uninstall will work like a charm but I would like to know how to make it work without running it as administrator.I mean all other applications can be uninstalled just fine and they are not running as administrator. Also the uninstall will work flawlessly on Windows XP but that was something to be expected. The problem happens both in Vista and Windows 7. In Vista I even get an UAC prompt and after I confirm that it still tells me that I don't have sufficient access.