I have the exact same problem, the "Add Item" link is not appearing on the frontend. I can see an empty div where it should be
"Edit Item" works fine.
I'm using Joomla 2.5.4 and the current version of K2
I can see the code in the category.php file that should make it work:
<?php if(isset($this->addLink)): ?>
<!-- Item add link -->
<span class="catItemAddLink">
<a class="modal" rel="{handler:'iframe',size:{x:990,y:650}}" href="<?php echo $this->addLink; ?>">
<?php echo JText::_('K2_ADD_A_NEW_ITEM_IN_THIS_CATEGORY'); ?>
</a>
</span>
<?php endif; ?>
but maybe there is a bug?