Tarun waits :)

I just tested it in a brand new installation and it is working as intended.

Tarun, which other extensions are you using?

Thank you for taking the trouble of new installation and testing.
I believe I am not using any extension other than that I explained above. (i.e Additional Categories for K2).

I will install joomla and K2 afresh and let you know what I did and the result.

Can you try disabling this and try with a brand new user?

Well, as it has been found out the quick_start pack of MAGAZINE template by GavickPro disables the K2 User login. Enabling K2 User Profile in K2 parameters (advance tab) solved my problem, since K2 user Registration Form has gender selection option in it.
I am not sure but it seems like if you Register with default Joomla Registration Form, K2 Comment Form won't appear after your login since it does not give you any gender selection option. And without a PROPER gender K2 won't recognize you. Genderneutrals are strictly prohibited in K2. :D

Hahahaha, the way this thing is going we should add a 3rd (or 4th option) in that selection.

Just kidding but thank you for pointing this out. We will look into it.