Regarding the fix, i think you need do put an fa- prefix before the icon name and you will need to add it to both link references, in the macro, and in the initial loop. Also let's put it in the <a> tag as well
{% macro loop(page) %}
{% for p in page.children %}
{% if p.visible %}
{% set current_page = (p.active or p.activeChild) ? 'active' : '' %}
<li class="{{ current_page }}">
<a href="{{ p.url }}">
{% if p.header.icon %}<i class="fa fa-{{ p.header.icon }}"></i>{% endif %}
{{ p.menu }}
</a>
{% if p.children.count > 0 %}
<ul>
{{ _self.loop(p) }}
</ul>
{% endif %}
</li>
{% endif %}
{% endfor %}
{% endmacro %}
<ul class="navigation">
{% if config.themes.antimatter.dropdown.enabled %}
{{ _self.loop(pages) }}
{% else %}
{% for page in pages.children %}
{% if page.visible %}
{% set current_page = (page.active or page.activeChild) ? 'active' : '' %}
<li class="{{ current_page }}">
<a href="{{ page.url }}">
{% if page.header.icon %}<i class="fa fa-{{ page.header.icon }}"></i>{% endif %}
{{ page.menu }}
</a>
</li>
{% endif %}
{% endfor %}
{% endif %}
</ul>
If you still don't see the <i> tag in between the <a> tag of the menu items, you might want to try a bin/grav clear-cache to flush the cache.
Here it is in action:
http://polydeon.com/monosnap/Blog__Demo_2014-11-16_22-29-53.png
Should work fine!
P.S. I think this is so useful i have added it to the antimatter theme:
https://github.com/getgrav/grav-theme-antimatter/commit/5b39fd6ad9a585180f3d485591a2560ebe3140a0