At what point during a typical request does the $wpdb object become available?

Please, post your code because the problem is not the one you guessed.

Actually, $wpdb is available very early: it is inited by the function require_wp_db() located in the file wp_settings.php at line #79.

The hook 'plugins_loaded' is fired in the same wp_settings.php file, but at line #237, so pretty after $wpdb is available.