Cisco router running NAT refuses to let certain hosts through

[ATC]

Some but not all hosts on a network are able to access the Internet via a Cisco router running Network Address Translation (NAT)

When trying to ping/traceroute hosts on the internet, the router returns "host unreachable"

There are no access-lists, or the access-lists have been double checked to make sure they're not blocking valid traffic.

[ATC]

Verify that overloading is enabled. Without using overload, the NAT mechanism will only be able to support N simultaneous hosts, where N is the size of your ip nat pool.

Since NAT can be configured in many ways I will not go into the full setup here, but instead show you a few variants of the config line in question.

Example 1:
"ip nat inside source route-map nonat pool mynatpool"
Use instead:
"ip nat inside source route-map nonat pool mynatpool overload"

Example 2:
"ip nat inside source list 10 pool mynatpool"
Use instead:
"ip nat inside source list 10 pool mynatpool overload"

Example 3:
"ip nat inside source route-map nonat interface Serial0"
Use instead:
"ip nat inside source route-map nonat interface Serial0 overload"