Problem and solution (yay!).
Problem: I installed a StreetMap Premium evaluation license (named ntna_2009.1_wa_all_10_14_09.sdlic). Initial installation went fine (dbl-click, got a confirmation that install was fine). I then purchased a full license and went to install that (named ntna_2009.1_wa_all_11_30_10.sdlic), but when installing got the error dialog stating "Data license installed is not configured properly. Try reinstalling application."
Solution:
Raj T at ESRI technical support led me through the process of deleting the file C:\Program Files\ESRI\DataLicense\st25000699.sdlic, which was "actual" license from the evaluation version. Once I did that I was able to run the installation of the full license.
Recommendation to ESRI:
Please include these troubleshooting instructions in the QuickStartGuide.htm on the installation media.
