If you are using Custom List Form SharePoint control to edit/enter metadata for your document library, documents will not get automatically checked in upon document upload thus preventing workflows to start.
Here is the situation I had to deal with:
A document library is set to "Require documents to be checked out before they can be edited?" to "Yes". under normal circumstances, when you upload a document on the EditForm.aspx you would have two buttons "Check in"(it would save the metadata associated with the document and check the document in) and "cancel" (which would discard all metadata changes, keep in mind that it does not discard the doc it's self) on top of the form as well as on the bottom.
if the library is set "Require documents to be checked out before they can be edited?" to No when the document is uploaded on the editform.aspx you would have instead of "Check in" button a standard OK button.
If you are using a Custom List Form SharePoint control on the EditForm.aspx, and "Require documents to be checked out before they can be edited?" is set to yes, on top of the edit form you will see "OK" button and on the bottom "check in" button alongside with the standard "cancel". One would presume that clicking the "Check in" button would check in the document.
Unfortunately it does not happen, neither clicking the "OK" button checks the doc in, which results to workflows not starting, because the document does not automatically gets checked in.
I'm not sure if it's a BUG, if it is then for some reason I could not find any information of this.
Only setting this doc library not to require document check out fixes the problem. but quite often it's not a desired functionality.