My first instinct is that the forwarding/NAT on machine C is a little confused.
How are you configuring iptables ? I had hell on a stick a few years back with SuSEFirewall (it hated having a dynamic address on the untrusted side) You possibly have an iptables statement somewhere that sets up the masquerade that may still have the external interface defined as ppp
Either that or name resolution does not work somewhere along the line, either in resolving the name of the gateway "C" in your example or in resolving the name of the Internet address.
Does it fail equally for a internet domain as well as an Internet address ?
What happens when you trace the route ?