I'll mark this thread as... something...
]]>Also make sure that you've got IP forwarding enabled:
echo "1" > /proc/sys/net/ipv4/ip_forward
As I mentioned, I followed the wiki guide on setting up the connection sharing... that step was specified in the wiki guide... Additionally, I wouldn't be able to ping external IP addresses if I hadn't performed that step (which I am able to), so again... best as can be observed, the issue is that for some reason the device cannot receive responses to DNS queries behind the NAT.
]]>echo "1" > /proc/sys/net/ipv4/ip_forward
]]>