I have visited Zanzibar four times, most recent in 2004. By this time the Island was quite politically unstable and some areas was not safe visiting, the northern half for exampel.
Areas worth visiting for birding on Zanzibar is very limited, common species such Indian pheasants, house crows, house sparrows and different kinds of egrets can be seen all over the Island.
I have found the forests 4-5km north of Stone Town quite good birding spots, with African paradise-flycatchers, Zanzibar bishops and several species of sunbird.
Jozani Forest Reserve (Southern Zanzibar) is probably the best birding area on Zanzibar, virtually all native forest that now remains on Zanzibar are found in and around this reserve.
Species such as Fishers Turaco (a near endemic) and Brown-headed Parrot are found here, 195 of Zanzibars 220 recorded species have been seen in this forest. Mammals such as blue duiker, Aders duiker, brush-tailed mongoose and Red colobus are all common here.
During my visited I have paid ocal people to guide me in the forest, there is plenty of them happy to assist you and they have great knowledge about the forest.
I would say that Jozani is the only spot on Zanzibar were you get an idea about how most of the Island used to look like once. With out no doubt the best birding spot on Zanzibar.