After working closely with the other end, we were able to get a tunnel going by not using NAT. Once we removed that, and change their configuration accordingly, the tunnel came up.
The only problem now, is that only their end can bring the tunnel. Whenever my end tries to initiate the tunnel, it gives Phase2 errors. The wonderful "NO PROPOSAL CHOSEN" error ID.
Would anyone know what I'm doing wrong in this situation? I have confirmed on their end that the tunnel is configured as Bidirectional, and should be able to be brought up from either end.
Not sure if it matters, but I am connecting this tunnel to a Cisco ASA.
Thanks,
Daryl