I'm thinking they should completely ditch ship fuel as a game mechanic. Not really sure what it adds to the game. I'm not having trouble finding fuel, especially in the later tiers. It just feels like it's there for its own sake. It's not an interesting part of the game to me, just a limiting one. What would you do if you had infinite ship fuel? Would you play the game differently than you already do?
I see it as just a currently incomplete mechanic that can eventually be interesting. The main problem right now is all stars are equidistant and coal is an overly used resource.
There's a few ways they could approach it. One possibility is to link it to progression. Personally, I am not a fan at all of the very distinct tiers guarded by a single craft item.
Fuel, creatures, and environment should be the barriers to expansion and progress. You start on a fairly friendly world without much threat. Coal, wood, and other organic matter should give you a tiiiny amount of fuel. Say keep it like it is with Coal giving 2 fuel units. Traveling to other planets in your system could then take say 50 or so fuel.
Traveling to distant stars, however, could be more in the range of 1 million fuel. Tech upgrades along the way would allow you to refine higher quality fuel from more resources. Imagine, say, setting up a drilling operation down in a planet core to just pump all that lava into your ship's engines providing hundreds of thousands of fuel.
In addition, planets should have much higher and deadlier environments and creatures. Planets with oceans of acid. Planets without oxygen. Planets with winds that slam you into a mountain and kill you. All kinds of things that kill you basically immediately upon landing unless you have built the property technology to deal with them.
This way, you have a more natural progression of:
1. Primitive technology, frail, stuck on your planet
2. Basic tech, light armor, able to explore your planet and surrounding planets
...
n. High tech, a god of combat, travel the stars freely without care for silly ideas like fuel and wildlife.
n+1. Build a house inside the acidic volcano of doom shooting lightning.
In this sense, there wouldn't be hard coded tiers really but a scale of easy to difficult planets to explore/colonize gated by your steadily growing technology and resources.