Rwanda has a classification specifically for technology entrepreneurs. It's a 3-year visa and if you are a qualified software practitioner, I don't foresee you having difficulty getting a permit to start a software company here. They also pride themselves on same-day business registration.
My main concern in this question is that I've heard of a growing concern in East Africa that foreigners are taking jobs/money out of the country instead of investing. From what I've heard, Rwanda sounds perfect, though Kenya has pretty amazing infrastructure too. Kenya is however a lot more dangerous than Rwanda sounds.
I've certainly heard some of that, but I don't think it applies quite as much to tech entrepreneurs -- and I've seen more evidence of that in say, Kenya. If you are coming here to build a software company, I would be surprised if Rwanda's arms weren't opened pretty wide.
At this point, Nairobi has more going on in it's tech scene and certainly a more mature market to sell into, but you are right, it's definitely not as safe and transparent as Kigali.
We are both college dropouts, so the first go around took a bit of convincing, but since we had a pretty lengthy work history we convinced them in the end. After that it has been smooth sailing, Rwanda is pretty friendly to foreign investment in general.
Was it easy to get a work permit / visa for Rwanda?