So... I've been running many versions of IOS on many routers and never had any problems with CBAC Firewall, NAT, public IP on the outside, private range on the inside - fairly straightforward. On this particular router, I've been running software with the IP/FW/IDS PLUS IPSEC 3DES feature set from probably 12.2.8T through 12.3.3a with no problems, the configuration hasn't really changed much.
However, with my working configuration on 12.3.3a, I tried out the new Nov-17 build of 12.3.5 and mysteriously none of my outside NAT translations go through to internal machines. I verified that there is no access list denying the packets on the outside interface - specific ACL permits with log showed this, and the NAT translation was being created according to debug as well... I spent 30 minutes trying to figure out what was going on.. I reloaded the old 12.3.3a IOS with exactly the same configuration and it works fine now.
Is this a bug? I did find this very strange.