If you share two connections via NAT under Linux (see section 10 of Linux Advanced Routing & Traffic Control HOWTO for instructions on how to do it) and the outgoing route is chosen at random, you may get into problems if the station beind the NAT router uses TOS. The route chosen by the routing stack depends of the originating IP, the destination IP, the TOS and the mark. That is if you start a connection between two machines at normal TOS and switch to Maximize-Throughput, the route chosen by the router may be through the wrong provider and as most provider now filter packets coming with an invalid IP, your traffic may be sent to a blackhole.
The simple fix in this case is to reset any TOS to normal into the prerouting stage of iptables.
More information (including iptables rules) coming soon.