I spent 10 days in Uganda in October with time primarily spent in Kampala and the west / south-west of the country before heading into Rwanda. I was visiting and travelling with my partner who was working for an NGO for 2 months in Kampala.
Absolutely no reason not to go there, particularly if you're heading into the mountains. Not sure where "murdery" comes from. It's Africa, so normal precautions apply but I found the people, the vibe and the country as a whole very welcoming.
We used a very professional and helpful company for our travels, competitively priced too -
http://www.rwandagorillatrekking.com/. I think they also organise trips to the Rwenzori.