If the key was used already or if you somehow got a retail copy with a duplicate key, that key can't be used again. The retail store should allow you to exchange it for another copy. I am sure that you are entering the key correctly as you would receive a different error if you entered an invalid key.
You can contact support to confirm that the key is already in use.
How to reach support (FAQ) - http://social.microsoft.com/Forums/en-US/onecareinstallandactivate/thread/30400b52-7f26-4ba0-bc18-17e305329d90
-steve
Microsoft MVP Windows Live / Windows Live OneCare & Live Mesh Forum Moderator