I have a similiar issue. My configuration is the following:
VPN Client -- PIX -- Router -- ISP -- Router -- PIX
I'm siting behind left PIX with VPN Client. If I configure left PIX to do address hiding with range of addresses (NAT) I CAN established the tunnel. But if I configure left PIX to do address hiding with one address (PAT) I CAN NOT establish the tunnel. In that case I receive in syslog form left PIX "Deny inbound (no xlate) protocol udp/500 on interface outside".
You should check syslog messages from your 800 Router doing NAT.
In "IPSec VPNs in depth" document, there is a good explanation of using NAT after IPSec, and there Cisco says that some devices do not handle properly VPNs if PAT is used (are we speaking here of Cisco routers and PIX firewall?).
Another possibility is to try IPSec over TCP, but I did not manage to do it. What should I configure on right PIX in order to achiueve this.
Cisco guys, where are you? We need you ...
Sasa Vidanovic