I found a way to fix this (at least for us). When redirecting to the accounts.google.com/o/oauth2/auth url, we had to add both approval_prompt=force and access_type=offline. If one was missing, we got no refresh token.

This url documents all of the parameters, but says nothing about the refresh token: http://code.google.com/apis/accounts/docs/OAuth2WebServer.html