you said that you were connected via ethernet cable, not wireless
right? so that excludes wireless problems.... the prior question about
setting up DNS seems relevant except you said this problem is with nat
enabled. Do you mean to say that you don't have that problem with NAT
disabled?