We have done the stretch from Mbala (Zambia) up to Bukoba (Tanzania) a few weeks back and have not encountered any problems. Here a quick description of the roads:
Mbala (Zambia) to Sumbawanga (Tanzania) - The road from Mbala to the actual border (some 20km) is pretty bad, took us about 1 hour, but doable (at least in the dry season). We understood that there was no immigrations at the actual border so you have to do that in Mbala. We were told that there were also no customs at the bordercrossing so we got our Carnet stamped out in Mpulungu. When we arrived at the bordercrossing however, there were customs people and after some calls on the Carnet they let us through. In Tanzania there are immigrations and customs at the border.
The road from the border to Sumbawanga is ok, we did 50 kmph most of the time. They are working to tar the strech and have done quite some streches already although we were not yet allowed to drive on most of the freshly laid tar... Expect some 3 to 3.5 hours for this stretch.
Sumbawanga to Mpanda - again a lot of tar already laid but not yet allowed to drive on it so you end up driving on the old road which does not allow you to drive faster than 40 (we feel). The main road that goes through the Katavi NP was closed so you have to take a d-tour on the more western road through the NP. We actually went from Sumbawanga to Kipili (on the lakeshore, very nice break). The road from Sumbawanga to Kipili took us some 4 hours and was in ok shape.
Mpanda to Kigoma - Be prepared for a very bad road from Mpanda to Uvinza. The 180 km took us around 7 hours. Tons of potholes you have to dodge all the time. Only saw a few villages along the road so quite remote. We expect this road to be a lot worse during the rainy season. From Uvinza to Kigoma there is a brand new tar road (on which they allow you to drive!) that will take you to Kigoma in about an hour.
Kigoma to Bukoba (via Kasulu and Kibondo) - We were a bit worried about this stretch as the Dutch and UK travel advice advises against non-essential travel between Kasulu and Kibondo because of some armed robberies in the past and the refugeecamps along the road (according to locals, the last incident was some 4 months ago). We did not feel insecure at any moment although we did see some military presence along the road. The road itself is good dirt where we did about 60 kmph and the last 200km to Bukoba is tar.
There is a lot of work being done on these roads, especially the bit from the Zambian border to Mpanda, and the tar stretches we've encountered were promising. There's no telling when they will open up more stretches of tar, but this could be soon. Only the Mpanda-Uvinza stretch showed no hope for improvement in the near future.
The lake is beautiful though, and there are some nice stops on the road (Kipili Lakeshore Lodge and Kigoma Jakobsen Beach). If you want to visit Mahale or Gomba, be prepared to pay
. If you want to avoid the poor roads, but still enjoy the ferry, it is possible to take cars on the ferry (make sure you agree on a price not only for the trip, but also for offloading...) but you can only travel between Mpulungu and Kigoma. It's not possible to get your car off earlier. It may be possible with motorbikes (they have to be unloaded with a crane in a small motorboat to get off at other locations), but we are not certain.
Enjoy!