Not to discourage you, but much of your route through the northern half of Kenya and into Ethiopia is highly unstable at the moment. Instability in northern Kenya (including Moyale which is shown as part of your proposed route) and many parts of Ethiopia (along the Kenyan and Somali border in particular) have resulted in many western countries categorically advising against any travel in those regions at all. There have been kidnappings in those areas.
I have traveled to some countries where certainly the state department warnings did not reflect the realities on the ground (that is, they were overblown) but this stuff is pretty serious and westerners are a key target for kidnapping. For some it is akin to pirate activity in the Indian Ocean where captors are seeking ransom, but in other cases it is islamist militant activity. This is especially true in the Somali, northern Kenya, southern Ethiopia region. So, be cautious.
I lived in Uganda for a year and a half in the mid 1990s and had a tremendous experience. Personally I never experienced any kind of trouble crime-wise, but I did know some who did, especially those travelling upcountry by themselves (or at least as the only American). Highway robbers are real, though the three cases I knew of did not involve any violence. In one case, the guy was left literally standing on the side of the road in his underwear as the thieves stole everything else, including the van the group was traveling in. Again, not frighten you off, but just to alert you to the potential dangers of traveling alone or in a small group by bike.
I will mention, though, that while I was there a group of doctors from, I believe, Canada passed through on a trip to raise awareness and money for health issues in the developing world. They were biking from Algeria to South Africa and in different legs of the journey picked up local riders for a while. A Ugandan friend joined them from Kampala to Tanzania. I had dinner with them and they had some pretty outrageous stories of close calls and scary situations, but at least at that point in the journey no one had been injured or robbed.
Certainly my experience in Uganda was that the vast majority of local folks were outrageously gracious, accommodating, helpful, friendly and just plain delightful. And I have no reason to feel this would be any different in the neighboring countries. But word travels fast when you are a foreigner and those who might have nefarious intent will find you quickly, so be safe!
Your route does not go through Rwanda at this point, but there is a national cycling team there. This seems like the kinds of groups you might want to connect with to identify routes and get some local support for repairs, resources, etc.
http://teamrwandacycling.org/
