This may be a silly question but you don't mention whether you've done this or not. I have had issues with configuring NAT on Cisco devices whereby I've had to clear the translation tables to get it to work properly ...clear ip nat translation force...