I have a number of co-workers who are unable to use track changes. We are using Office 2013. I have turned on the track changes and set it to All Markup but nothing they do in a document shows a strike through, underline, or any other mark. Any ideas what the problem could be?

Is it possible they don't have Review/All Markup selected? Just a thought.
It's not clear from what you wrote, whether you are working on a shared drive, separate copies of the document, etc. Clarification would be useful.

This is happening on individual computers on any document they try to track changes on. Nothing is being shared. They are not working on the same document. I have checked both computers and made sure that Review/All Markup is selected.

The only other possibility I can think of, is that under Show Markup, nothing relevant is checked, but I'm sure you have also looked there. Have you reviewed the full track changes dialogue? This is opened from the tiny down arrow, bottom right of the Tracking segment of the Ribbon. IT will open a small dialogue with an Advanced button. Check through both.

Hope this helps.

Yep, looked through all of that too. Beyond frustrated at this point