The fallback_cb argument is used when the menu doesn’t exist– that is, when there is no menu of the right name. I won’t be used otherwise. Check the Codex. By default the fallback is wp_page_menu.
Your code looks right to me for using a class method as the callback, but I suspect that what you really want is the walker argument, not the fallback_cb one. The walker argument will be used any time that your menu is created, not just as a fallback if something goes wrong.