Did you setup the default gateway and the DNS Server specifications in your Linux box?
I am running Winproxy as my proxy server on NT for my local network's gateway to the internet. I had to setup all of my machines to use the gateway for email and internet to work properly.
You shouldn't have to do anything to sendmail. All of your setup can be done using Linuxconf in the Networking section.
Good Luck.