I am unable to refresh an access_token using the rest api.  I am making the following POST:

POST /services/oauth2/token HTTP/1.1
Host: login.salesforce.com
Content-Type: application/x-www-form-urlencoded

grant_type=refresh_token&client_id=<cid>&client_secret=<cis>&refresh_token=<rt>

with appropriate vales for <cid>, <cis> and <rt>.  I am getting a 400 error with the following values returned:

{
"error": "invalid_grant",
"error_description": "token validity expired"
}

Does anyone know what is going on?  When I pass in a known invalid refresh_token I get a different error:

{
"error": "invalid_grant",
"error_description": "expired access/refresh token"
}

So, I think my refresh token is valid.  I can't find any information explaining the meaning of "token validity expired".  I have tried the refresh immediately after receiving the refresh_token and after waiting for a few hours.  Any help would be appreciated.