Can you detail how exactly you obtain a new access token? Are you using the OAuth refresh flow?

Probably the easiest way to confirm that we're following the OAuth refresh flow is with the code.  I included most everything except the Post() function that we call in a class called HttpTools.

We pass a rest url into the first function below, such as:

https://na12.salesforce.com/services/data/v24.0/chatter/feeds/company/feed-items

The refresh token, client (consumer) id, client secret are in .config file and moved into the appropriate variables a ways down in RefreshAccessToken(). 

The refresh url, also used in RefreshAccessToken(), is:

https://login.salesforce.com/services/oauth2/token

       private string get(string url)
        {
            string response;

            // if access token not yet initialized, do so now
            if (string.IsNullOrEmpty(msAccessToken))
                RefreshAccessToken();
            
            response = makeCall(url);

            // if exception or unauthorized, refresh access code and try again
            if (response == string.Empty)
                RefreshAccessToken();
            else
                return response;

            response = makeCall(url);

            if (response == string.Empty)
                throw new ChatterAuthorizationException("Access Token Failure");
            else
                return response;
        }

        private string makeCall(string url)
        {
            try
            {
                HttpTools httpTools = new HttpTools();
                httpTools.Headers.Add("Authorization: OAuth " + msAccessToken);
                string response = httpTools.Get(url, string.Empty);

                return httpTools.LastResponseCode == HttpStatusCode.Unauthorized ? string.Empty : response;
            }
            catch
            {
                return string.Empty;
            }
        }

        public void RefreshAccessToken()
        {
            var httpTools = new HttpTools();
            NameValueCollection form = new NameValueCollection();
            form.Add("grant_type", "refresh_token");
            form.Add("client_id",msClientId);
            form.Add("client_secret",msClientSecret);
            form.Add("refresh_token", msRefreshToken);

            string url = msRefreshUrl;
            string response = httpTools.Post(url, form);
            JObject responseJson = JObject.Parse(response);
        // get new access token and refresh instance url
            msAccessToken = responseJson["access_token"].ToText();
            msInstanceUrl = responseJson["instance_url"].ToText();
            AccessTokenHasBeenRefreshed = true;
        }

        public string Get(string url, string queryString)
        {
            HttpWebRequest req = (HttpWebRequest)WebRequest.Create(url);
            req.Method = "GET";

            if (Headers != null && Headers.Count > 0)
            {
                foreach (string header in Headers)
                {
                    WebReq.Headers.Add(header);
                }
            }
            HttpWebResponse resp = (HttpWebResponse)req.GetResponse();

            LastResponseCode = resp.StatusCode;
            return ReadResponseStream(resp);
        }

Off the top of my head, I can only think of one case where a 503 is issued and that is when you've run into the hourly rate limit. The current limit is 200 requests/OAuth consumer/user/hour. Is it possible that this has nothing to do with a token refresh and you're just hitting the rate limit? That might also explain why this seems worse lately -- if you're doing more stuff you might be using up your rate limit quicker.

Thanks, it is very possible that we are hitting that limit while testing.  I will keep it in mind.