I ran into this problem when I didn't explicitly request "offline" access when sending the user to the OAuth "Do you want to give this app permission to touch your stuff?" page.
Make sure you specify access_type=offline in your request.
Details here: https://developers.google.com/accounts/docs/OAuth2WebServer#offline
(Also: I think Google added this restriction in late 2011. If you have old tokens from before then, you'll need to send your users to the permission page to authorize offline use.)