I've played with this a little bit trying to work with, what I think is the V1 stuff, that you were using and this seems to work...
ContactsService cs = new ContactsService("");
cs.setUserCredentials("username", "password");
string token = cs.QueryAuthenticationToken();
ContactsService cs2 = new ContactsService("");
cs2.SetAuthenticationToken(token);
var results = cs2.Query(new ContactsQuery(ContactsQuery.CreateContactsUri("default")));
It may not be the most correct way to do this (I suspect what vicfryzel says is the way to go) but this may do what you want. The AuthSub stuff appears to be for web apps which is, I'm guessing, why your not using it.
The V2 documents do this a little differently than the way V1 docs do:
RequestSettings rs = new RequestSettings("app", "user", "password");
ContactsRequest cr = new ContactsRequest(rs);
At the moment I'm not sure if you can get a token like you can with the V1 stuff but one of your comments mentioned using "Google API Ver2" so I thought I would include it.
I'm going to keep looking at this since I've been wanting to do something with this myself and I'll edit this answer with anything I find.