You have to play Federation for a few levels before Klingons are unlocked. It is some where around level 6-7 and it goes pretty fast.
They did this to only have one tutorial and so you can learn the basics of the game. Something else you probably need to be aware of is that Klingons are primarily a PvP faction at this time with very little PvE content. PvE is coming but not there yet.
There are two ways to unlock Klingons that I know of. There's a quest you can do through Feds that unlocks Klingons. Or, when you hit level 6 on your Fed (Level you can begin pvp'ing...) , that's what I did. The nice thing is, when you create your Klingon they start at level 5 and very quickly hit level 6 in a few short quests on the base. As soon as you hit Level 6 you can just log out and you'll notice a new option to create a Klingon.