Are you using PostGRE? I know the old uc_addresses had some problems installing with PostGRE (it tried to create uc_orders instead of uc_addresses) and it could have had some problems with uninstalling as well. For that matter, so could the new uc_addresses. While I fixed the uc_orders problem, I don't have PostGRE installed nor am I familiar with it.

If you have MySQL, the problem is a mystery. I have run through the uninstall and install myself without any problems. Maybe I introduced a bug late in the game? Anyone else have the same problem (or not had the same problem)?