I've verified several videos have closed captions (within a browser on a computer) but when I load them on the Xbox it seems to think no closed captions are available.

I verified I had the correct video(s) by adding them to my "watch later" list on the computer then logging into Xbox live on the Xbox.