There are two solutions.
The simplest is have you database tables start with wp_.
Of course that is’t always an option, for example a multi-site install or a situation where you don’t control the host environment.
I looked around other parts of the code, and they use {$wpdb->base_prefix} when constructing the SELECT queries, but for the case of the custom menus the wp_ prefix is hard coded.
The offending line is #443 in admin/admin-panel.php
It is currently:
$menus = $wpdb->get_results( "SELECT term_taxonomy_id,a.term_id,name FROM wp_term_taxonomy as a,wp_terms as b WHERE a.taxonomy = 'nav_menu' AND a.term_id = b.term_id" );
To fix it I changed it to this:
$menus = $wpdb->get_results( "SELECT term_taxonomy_id,a.term_id,name FROM {$wpdb->base_prefix}term_taxonomy as a,{$wpdb->base_prefix}terms as b WHERE a.taxonomy = 'nav_menu' AND a.term_id = b.term_id" );
And bam, it worked. I’ve posted this to wptouch’s support board, and someone responded saying they would pass it on to the developers.
This problem also appears to effect multi-site wordpress installations.