Looking back at your post, it seems like you are trying to update a custom object that doesn't exist. The data structure needs to be defined in order to sync a custom object to a lead.
The relationship is one-to-many/many-to-many meaning you can push multiple entries to a custom object on a lead and they will exist in the Lead's Detail under the Custom Object's tab which can in turn be used to filter off a value of a custom object/trigger off the custom object being added to the lead.
The API you're referring to is only for creating and updating custom object records, we do not currently offer an API for managing custom object types.
ahh, you are right. There isn't a way to create the custom object type. Thanks for the help as I'm figuring out the same problem as Danielle. Any idea if that's on the roadmap (?)