Are you really sure you have a valid cd-key? I thought I did but it was just a demo key. 15 characters when it should be 16 characters. I had to buy a new game--$9.99.
I still had problems though, but all has worked fine since I went and deleted all the q3cdkey files. There were at least 6, 1 in the baseq3 folder, and each mod folder may have one also, i.e., F4A, FFA, OSP, Excessive, Berylium etc.