menu_tree_all_data() returns empty arrays for custom menus
Custom menu machine names always have a prefix of "menu-", e.g.:

$tree = menu_tree_all_data('menu-custom-menu');


Make sure you're using the right machine name. Edit the menu and look at the URL: The last part of it is the machine name for the menu.