I just had this issue a few days ago and a call to Cisco's support revealed the problem.
NAT doesn't appear to be the problem, but PAT is. It seems that if all available NAT addresses are taken, PIX will overflow to a PAT address, which it does not allow VPN traffic to traverse.
Bluecrack's suggestion about assigning a static IP address to the machine, then a STATIC statement on the firewall, is what was suggested to me, also.
Speaker