Are contacts from the Google account also stored on the phone? Are contacts stored in Google Contacts also stored on the phone or are they only accessible if the phone has a data connection?
A copy is locally stored, so these contacts are also available when there is no current data connection.