I had the same problem. First I deployed the custom object without the fields and hence the deployment failed. Then I came across this post, did not understand it well, but I assumed to add the custom fields of the custom object in the change set as well as the custom object and it worked. So we need :

1. the custom object to be added to the change set
2. the custom fields of that custom object to be added as well to the change set.

I just don't know why salesforce are separating the custom fields from the custom object. Thans sridhar for the hint

I had the same problem. First I deployed the custom object without the fields and hence the deployment failed. Then I came across this post, did not understand it well, but I assumed to add the custom fields of the custom object in the change set as well as the custom object and it worked.

So we need :

1. The custom object to be added to the change set
2. The custom fields of that custom object to be added as well to the change set.

I just don't know why salesforce are separating the custom fields from the custom object. Thans sridhar for the hint