From what I can tell then, it seems the most likely answer is that you aren't using the "Completed" stage in any of your workflow activities. Just having it defined may not be enough. The only way I've been able to reproduce what you're seeing is to not have the stage used.

I took one of my workflows, set it to workflow driven, and then removed all of the "completed" stage from all the activities that had it, and "Completed" it is not appearing in the list of stages, much like your screen shot. I then added it back and it is appearing again. (Something to keep in mind, whether you are new to the platform or have been in it for a while) is that once a workflow has been started, it will run on the same workflow version as it started. If you check it out and change it, you are creating a new version. You'll have to create a new item to test.

If you haven't seen the wiki (older documentation, but seems to be a little more complete than docs on this topic), see http://wiki.servicenow.com/index.php?title=Workflow_Stages#gsc.tab=0 .