As long as you have at least "Add" rights to that Contacts list, you
should see the NEW button.
By default, Contributors can add items. You might want to double check
your permissions on that list itself, and you're right, if you have Full
control, you should definitely see the NEW button.