É verdade que a versão em linha do Vocabulário Ortográfico da Língua Portuguesa da Academia Brasileira de Letras regista majorina como substantivo feminino, mas é também verdade que a palavra não vem acompanhada de nenhuma indicação que nos garanta claramente que se trata do feminino de major. Também posso confirmar que nem o Dicionário Houaiss nem o Dicionário Aurélio XXI acolhem este termo. Além disso, verifica-se que a palavra majorina não ocorre em corpora para análise linguística e surge escassamente em páginas não tratadas da Internet.

Por conseguinte, recomendo que continue a usar a palavra major para os dois géneros: «o/a major.» O mesmo me parece ser de aplicar a tenente: «o/a tenente», seguindo o modelo de presidente.

Quanto a cabo, já a questão se complica, porque é muito estranho manter o índice temático da palavra que marca tipicamente o masculino e depois combiná-lo com a forma feminina singular do artigo definido: «a cabo». Não obstante, parece que é assim que se usa a palavra quando aplicada a um militar do sexo feminino.