Hi Stephen,
There could be a variety of factors contributing to this problem depending on what your Course Completion criteria are. Have a look at the Completion tracking for a course which shows as started, and one which shows as not.
Also the Course Completion report for each of the courses worth looking at:
Home>category>course>reports>course completion
If its still unclear could you forward me screenshots of each and Ill have a look?
regards,
George.