Most wp_nav_menu parameters ignored

The reason for your not being able to use before and after is because when you’re calling wp_nav_menu() with a default fallback of wp_page_menu(), which does not have a before and after arguments.

Refer to line 171: http://core.trac.wordpress.org/browser/tags/3.2.1/wp-includes/nav-menu-template.php#L137

Apparently the menu you are trying to get does not exist (has no items) the !$menu is true. Make sure you have created a menu in Appearance > Menus and set it to a default one, or query for an existing one, or customize the fallback function, otherwise wp_page_menu will be called, simply listing all the pages.