Linear rheological properties of tightly-entangled isotropic solutions of semi-flexible polymers are calculated using a tube model, and qualitative predictions are given for the response of more dilute solutions. The linear complex modulus of a solution of long, tightly-entangled chains is dominated at low frequencies by a curvature contribution, analogous to the elastic stress of entangled flexible chains, that relaxes by reptation and gives rise to a broad elastic plateau. The modulus is dominated at higher frequencies by a larger tension contribution, whose frequency dependence is controlled at intermediate frequencies by the diffusion of excess length along the tube and at very high frequencies by the unhindered transverse motion of the chain within the tube. This high-frequency regime yields a complex modulus that varies as G*(omega) proportional to (i omega)(3/4) With frequency omega. Solutions of shorter, rod-like chains also exhibit a slowly-decaying orientational contribution analogous to the elastic stress found in solutions of true rigid rods. The Linear response of the flow birefringence and the effect of cross-links between chains are also discussed.