You've got a mixed bag of symptoms there that, admittedly, don't really have a lot to do with Active Directory. I tend to think that, at the root of it all, you're having some kind of name resolution problem, but there's not enough in your question to ascertain that.
What does a traceroute to an Internet IP address (use something like "8.8.8.8" if you don't have a known-reachable Internet IP handy) from one of the Linux machines look like? Are your packets making it beyond your network?
What does an nslookup using a known-resolvable Internet name look like from one of the Linux machines?
What does an nslookup using the Active Directory domain's name look like from one of the Linux machines?
Edit:
re: Your concern with name resolution - Your company's domain name is resolving to the IP address of your Active Directory domain controller because you named your Active Directory domain using your company's domain name. This isn't a best practice (see Choosing local versus public domain name for Active Directory for some discussion) and will make it impossible to resolve your company's domain name to the Internet IP address hosting services for that domain. (You really should think about changing the domain name to be a subdomain of your company's domain name. Insert religious argument with Brian Desmond about how "big companies do this all the time" here...)
I'm not clear what role "LINUS.innovisit.com" is playing. If that's your Internet router then your packets aren't getting further than the router and that would be the place to start looking.
I don't understand what you mean when saying "...I will get a connection for a minute or two, then I lose it again." By "connection" I think you are saying that you're able to access some Internet resource for a brief period. That strikes me as very odd. My gut says that something oddball is going on w/ your router, or you're having an IP address conflict with an important host like the DNS server, the router, or the Linux machine you're testing from. More specific diagnosis is going to be difficult, I think, from here.
Edit 2:
I don't know what the problem is, and I didn't say "the problem is the router". I think you have something really odd going on because the symptoms you're reporting don't point to a common cause.
You're to the point where, were I on-site, I'd be sniffing traffic.
I'd start sniffing traffic between the problematic Linux machine and the rest of the LAN (if only with tcpdump on the Linux machine itself) to see if the traffic is making it to the LAN. I'd also sniff between the router and the LAN (with either a port mirror or a bump-in-the-wire sniffing rig) to see if the packets from the Linux machine are making it to the router. You could also sniff on the outside of the router to see if its packets are making it out but getting mangled in some way.
