Is this too long for a web request?
You could use guard statements and extract out the switch(response.StatusCode) block to a method. Furthermore, I'd replace the three-letter magic strings with constants. Their name could come from the comment around the magic string (UP_TO_DATE for "UTD" etc.). It would make the comment(s) unnecessary.

private Exception CreateHttpStatusException(Request Request, HttpWebResponse response) {
        switch (response.StatusCode)
        {
            //Generated by web app
            case HttpStatusCode.BadRequest:
                return new ArgumentException(String.Format("The Request passed to CheckForUpdate was incomplete: AppName:{1}; Channel:{2}; Version:{3}", Request.AppName, Request.Channel, Request.Version));
            case HttpStatusCode.Unauthorized:
                return new UnauthorizedAccessException("The serial number for this application was invalid.");
            case HttpStatusCode.ServiceUnavailable:
                return new AppDomainUnloadedException("The web service is currently unavailable.");
            //Common server errors
            case HttpStatusCode.NotFound:
                return new FileNotFoundException("The updater server page could not be accessed.");
            case HttpStatusCode.InternalServerError:
                return new WebException("The web server encountered an error.");
            //Unexpected server errors
            default:
                return new ApplicationException("An unexpected error occured: " + response.StatusCode);
        }
}


public bool CheckForUpdate(Request Request)
{
    HttpWebRequest httpRequest = (HttpWebRequest)HttpWebRequest.Create(UpdateServerAddress + "http://{0}/update.php?{1}" + Request.ToString());
    httpRequest.UserAgent = "KMUpdaterClient/" + Assembly.GetExecutingAssembly().GetName().Version.ToString();
    httpRequest.Accept = "text/plain";
    HttpWebResponse response = (HttpWebResponse)httpRequest.GetResponse();
    if (response.StatusCode != HttpStatusCode.OK)
    {
        throw CreateHttpStatusException(Request, response);
    }

    string responseString = String.Empty;
    using(StreamReader sr = new StreamReader(response.GetResponseStream()))
    {
        responseString = sr.ReadToEnd();
    }
    response.Close();
    switch (responseString.Substring(0, 3))
    {
        case "UTD":
            //Application is up to date
            return false;
        case "AVL":
            return true;
        case "ERR":
            throw new ApplicationException("An error occured on the server: " + responseString.Substring(4));
        default:
            //Unexpected
            throw new ApplicationException("An unexpected response was recieved by the server: " + responseString);
    }
}