Processing of a clearance where circumstances are of an unusual or questionable nature can take up to 18 months dependent upon the nature and depth of research, secondary interviewing and investigation necessary to determine the nature and associated risk or those circumstances. This is a direct quote from my investigator when my clearance was being processed for DoD. My sin was being American, living in Canada and having travelled to Saudi Arabia on direct orders, Dept. of the Air Force, in support of Operation Southern Watch and later, Desert Fox. Something else to keep in mind is that mine was an upgrade of clearance and not an initial issue/investigation.
The time will vary depending on the case load and competence of your investigator and the priority of the request, if applicable.