Crap starting and general sluggishness could be unrelated.
Plenty it could be on a td5, none of which would be sorted with an engine rebuild.
Battery
Dodgy earth/chafed wiring
Starter motor
Crank position sensor
Starter arcing and interfering with CPS signal
Glow plugs
Glow plug relay/wiring
Injector loom
Injector seals (I know they've been done..)
Fuel filter
Fuel filter housing or it's internal bits
Fuel pump
Fuel pressure regulator
MAP sensor, wouldn't affect starting though ime, definitely sluggishness
MAF sensor as above
Coolant and fuel temp sensors, though I don't think they would stop it starting, only the CPS will kill a td5. May be wrong.
Plenty to investigate, all stuff that wouldn't be covered with the rebuild apart from injector seals and injectors.
Cracked head?