I just hit something similar when I was pulling all columns for Contact and then trying to re-insert the object in another sandbox:
Unable to create instance of the deserializer shared.xml.soap.serialization.BeanDeserializer for type: class common.api.soap.wsdl.Address and element: null
When you fetch all columns for Contact, the address fields are returned separately (MailingStreet, MailingCity etc) and (since API 30.0) also as a compound field 'MailingAddress' which is a whole XML structure of its own. That is, its not just a compound string, its a whole load of seperate fields in their own 'object'.
Looks like support for serializing or deserializing these compound fields is lacking in some places in the API - I was getting the error when trying a create() call against the partner API.
As you say, the solution is to avoid fetching the compound field in the first place and just use the old separate fields.
The describeSObject metadata can be used to avoid these fields - if fieldType = address then its one of these compound fields and should (maybe) be avoided.
List<string> fieldNames = meta.fields.Where(f.type != fieldType.address).Select(f => f.name).ToList<string>();
... gives all field names for the object except the compound address fields (where 'meta' is of type DescribeSObjectResult as returned by the API)