You should use a key or token to identify a real player. When they create an account with your server, send back a token that uniquely identifies that player. Everytime they use your web service to submit a score, if their token is valid, send them a different one, and keep track of what you're expecting next submission, if for any reason you're sent back the wrong token, you can return a fault string or simply not update scores.
You should keep a log of which accounts are accessing your service and when, this way you can spot if someone is trying to mess with your WS, and if any score gets through that is not legit (which is highly doubtful if you use tokens), then you can take appropriate measures.