I'm beginning to suspect that there's a bug involving fuel consumption when a ship is being towed. I suspect that the fuel consumption rate is calculated as proportional to (ActualTGSpeed/MaxShipSpeed), rather than (ActualTGSpeed/MaxTGWithoutNebulaEffects) (I threw the nebula part in there based on others' reports).
[EDIT]
I just realized the above formula is wrong - "MaxTGWithoutNebulaEffects" should be "MaxTowComplexSpeedWithoutNebulaEffects", by which I mean the maximum speed of all the ships linked by tractor to the ship whose fuel consumption is being calculated.
[/EDIT]
I've got jump-gate construction ships which don't have many engines - max speed is 847 km/s with 381 days of fuel. Twice now, I've gotten a "low fuel" message while one of these is being towed by a powerful tug - the TG speed is 2392 (or roughly 3x). The first time I thought it was an oversight, but this time I'm 90% I checked that fuel was 100% before the journey started. One definite piece of evidence that something's wrong - my first "low fuel" message says the ship's at 6.8%, which means it burned at least 3.2% in a single 5-day. Given a ship with 381 days of fuel is ~76 5-days, which means that it should burn 1.4% fuel at most in a single 5-day (and I'm using 1-day increments, so the 5-day wasn't 10 days long).
It occurs to me that the tug is probably also burning fuel too slowly if I'm correct about what's going on....
John