One thought – when I go to www.example.com/staging/wp-admin it automatically redirects me to www.example.com/wp-admin
Could the redirect from staging.example.com to example.com/staging be conflicting with the existing install?
UPDATE: looks like it could be related to .htaccess issues and complicated domain references in the database
From the WP Codex:
Moving WordPress Multisite
Multisite is far more complicated to
move, as the database itself has multiple references to the server
name as well as the folder locations.The best way to move Multisite is to move the files, edit the
.htaccess and wp-config.php (if the folder name containing Multisite
changed), and then manually edit the database. Search for all
instances of your domain name, and change them as needed. This step
cannot yet be easily automated. If you’re moving Multisite from one
folder to another, you will need to make sure you edit the wp_blogs
entries to change the folder name correctly.