Hard to tell from a distance, but the fact that you can tether phone 2 is a good sign. Whe your Linux host connects, check the following and report back.
Check the IP configuration is as expected and a default route exists...
Let's see if a valid nameserver is present...
Code:
grep name /etc/resolv.conf
From that information we should be able to advise further.