I always do. Uninstall and also run Drive Sweeper. It helps get ride of the extra files and such. I also run C Cleaner for the reg clean. Both are VERY well know and used apps. Do this before uninstalling your video card. Download the latest drivers for your new card off the Nvidia site so it is ready for when you install your new card.
I've been using CCleaner for years, but never heard of Drivesweeper. I will certainly follow your advice to the letter. This new card is going in a brand-new machine, so I want to make sure nothing gets mucked up.
But to be clear, the order would be:
1) Run the Windows uninstaller for everything ATI.
2) Run Drivesweeper and the reg option on CCleaner.
3) Replace ATI card with the Nvidia card.
4) Install the pre-downloaded Nvidia drivers.
And after 3), shouldn't Win 7 shoot up a "new hardware found" message?