Lync Error "Sharing Failed Due To Network Issues"

I recently had a user that was getting a "Sharing Failed Due To Network Issues. Please Try Again" error when they initiated or received a Desktop Sharing session with another user in a remote office. Sharing worked fine with users in other locations, which at first I thought was odd.

The full error from the Reporting Server was:

22; reason="Call failed to establish due to a media connectivity failure when both
endpoints are internal";
CallerMediaDebug="application-sharing:ICEWarn=0x220,LocalSite=Local IP:19781,LocalMR=Media Gateway IP:54566,RemoteSite=Remote Ip:29987,PortRange=1025:65000,LocalMRTCPPort=54566,LocalLocation=2,RemoteLocation=2,FederationType=0

**Note** The IP's have been removed for security of course.

The details for a Diagnostic ID 22 are:

Call failed to establish due to a media connectivity failure when both endpoints are internal

Description: 
The call failed to connect because a media path could not be established between the two internal endpoints. This can be caused by network performance issues affecting the endpoints. Correlation of such failures with individual networks or endpoints can indicate potential deployment issues.

This problem always points to a network configuration issue, whether it's a firewall, ports not being open, etc.
In our case, there was no route between the VPN's that the two users were connected through. So, we created a tunnel and presto; Sharing works!