I’ve scanned over the oembed class and it appears to make a wp_remote_get() request to the various embed providers.
We’re still looking at our production machine, but my suspicion is that our firewall blocks the server from reaching, say, youtube.com to retrieve the oembed information.