To provide insights into how polymer-grafted nanoparticles (NPs) enhance the viscoelastic properties of polymers, we have computed the frequency-dependent storage and loss modulus of coarse-grained models of polymer nanocomposites by means of molecular dynamics simulations. Nanocomposites containing NPs grafted with chains similar to those comprising the host polymer matrix exhibit considerably higher moduli than nanocomposites containing bare NPs across the entire frequency range investigated. This effect is shown to arise from the additional distortion of the shear field in the polymer matrix resulting from the grafted chains and from the slower relaxation time of the grafted chains compared to the matrix chains when the former are at least half as long as the latter. Increasing the attraction between the grafted and matrix chains results in further enhancement in the two moduli, but only at frequencies slower than those corresponding to the longest relaxation time of the chains. This effect is shown to arise from a dramatic slowdown in the relaxation dynamics of both the matrix and grafted chains. In addition, the nanocomposite moduli are found to increase with decreasing NP size and increasing NP loading, grafted chain length, and grafting density with varying frequency dependence. These parametric effects are also explained in terms of shear distortion effects and chain relaxation times. Based on these results, a phenomenological model is proposed to estimate the storage and loss modulus of such nanocomposites as a function of the Rouse relaxation times of the grafted and matrix chains and the volume fractions of the NPs, grafted chains, and matrix chains. The model captures the observed dependence of the moduli with the examined parameters of the grafted NPs and yields moduli predictions that agree quantitatively with those computed from the simulations at low frequencies.