This is a common question from developer who is creating his/her first custom workflow for SharePoint.
Turn on "Create major and minor (draft) versions" on document library is definitely a right way to go :) But the problem usually fall in one of following two scenarios
Scenario 1 - Missing value in InitiationType Element
Make sure in your workflow definition (workflow.xml) you have included OnMajorCheckIn in <InitiationType>. For example
MSDN - "If you do not specify an InitiationType element, Windows SharePoint Services treats the workflow as if the Manual, OnNewItem, and OnItemUpdate values have been specified"
Scenario 2 - The option is enable to you, but you can't select it.
Since "major and minor versions" only supported in Document Library. "Start this workflow to approve publishing a major version of an item" option was never meant to work with List. So make sure you only associate your custom workflow to Document Library if you want it to work. If you do it via code, make sure this is how you do it:
SPList _list = _spweb.Lists["Documents"];
SPDocumentLibrary docslib = (SPDocumentLibrary)(_list)
//Add workflow to document lib not list
Hope it helps