The only problem reports I found with this warning message were for the free CDF Player.
Is CDF Player also installed on this computer? It is conceivable (not likely) that the passwords are
getting confused somehow.
To get a better idea what the Mathematica sees, please run these inputs and post them and their outputs.
The "outputs" below are just examples.
In[1]:= $ReleaseNumber
Out[1]= 1
In[2]:= $Version
Out[2]= 8.0 for Microsoft Windows (32-bit) (February 23, 2011)
In[3]:= $PasswordFile
Out[3]= (full path)
In[4]:= FilePrint[$PasswordFile]
(contents of the licensing file)