<p>I have a RESTful web service deployed at <a href="http://example.com/v1/SomeResource" rel="noreferrer">http://example.com/v1/SomeResource</a>. One day, a new protocol version (<strong>that is not backwards compatible</strong>) is deployed to <a href="http://example.com/v2/SomeResource" rel="noreferrer">http://example.com/v2/SomeResource</a>. From the client of view, this upgrade could occur at any time between two HTTP requests.</p>

<p>How does the server indicate to the client that it no longer supports v1 calls and the client is expected to upgrade to v2? Is there an appropriate response code I can use?</p>

<p>I would want to provide the client with the following information:</p>

<ol>
<li>An incompatible upgrade has taken place. There is no way for the client to use the new service because the protocol could be totally different.</li>
<li>The URL of the new client software.</li>
<li>A message explaining to the users that they must upgrade.</li>
</ol>

Best practice:
It's probably better to keep the versioning out of the URL and to make the new resources backwards compatible with the old.
Backwards compatible:
If you must keep the v1 in the URL, and are making v2 URLs, then you have to decide whether you want to support both formats, or make the old v1 obsolete.  If you decide on making the old v1 obsolete then I would recommend to return 303 or 401 for anyone requesting a v1 URL.
Making old URLs obsolete:
I would recommend using 303 See Other.  Or if there is no associated redirect, then use 410 Gone.
Source
303 See Other
The response to the request can be
  found under a different URI and SHOULD
  be retrieved using a GET method on
  that resource. This method exists
  primarily to allow the output of a
  POST-activated script to redirect the
  user agent to a selected resource. The
  new URI is not a substitute reference
  for the originally requested resource.
  The 303 response MUST NOT be cached,
  but the response to the second
  (redirected) request might be
  cacheable.
The different URI SHOULD be given by
  the Location field in the response.
  Unless the request method was HEAD,
  the entity of the response SHOULD
  contain a short hypertext note with a
  hyperlink to the new URI(s).
Note: Many pre-HTTP/1.1 user agents do not understand the 303
    status. When interoperability with such clients is a concern, the
    302 status code may be used instead, since most user agents react
    to a 302 response as described here for 303.
Document everything:
The main thing to be concerned about is whatever you chose to return, just document it in your documentation.  You can decide how you want your service to work, others that want to consume it will follow the documentation.