either reach level 6 on your fed, or finish the "Stop the Signal" quest. doing either one will unlock the ability to create a klingon (although you may need to relog/restart to see it).
your klingon will start at level 5 or 6 (don't recall which exactly) so it's not really wasted time. it's just that this way, Cryptic only needed to make the new player introduction missions for one side. it would be a waste of development time to make a whole other set of klingon-specific new player missions, and Cryptic is all about not making klingon-specific missions if they can reasonably avoid it.