The fact that the hex-encoded sortkey must be converted to binary format for prop=categorymembers cmstartsortkey and cmendsortkey has long been an odd wart in the API.
Bug 70690[1] showed that the binary values for these parameters is actively breaking on some wikis. In Gerrit change 159746[2] these parameters have been deprecated in favor of new parameters cmstarthexsortkey and cmendhexsortkey which take the sortkey in the same hex-encoded format that is returned by the API.
This change should be deployed to WMF wikis with 1.24wmf22, see https://www.mediawiki.org/wiki/MediaWiki_1.24/Roadmap for the schedule.
[1]: https://bugzilla.wikimedia.org/show_bug.cgi?id=70690 [2]: https://gerrit.wikimedia.org/r/#/c/159746/