Are we sure this means the key is invalid?
Same thing happened to me after I had just generated a new key.