Direct numerical simulations (DNS) of Newtonian and drag-reducing viscoelastic turbulent channel flows generate crucial data to analyze and understand the nature of turbulence and its modification due to viscoelasticity. Such an understanding is necessary to enable better drag reduction technologies. Previously (Samanta et al., Phys. Fluids, 21, 115106, 2009) we have shown that viscoelasticity can significantly alter the non-Gaussian character of the probability density functions (PDFs) of many of the turbulent statistics in the flow. In this work, we investigate further the non-Gaussian characteristics of the PDFs generated in viscoelastic turbulence by focusing on their tail behavior. In particular, we show that many of the tails of the PDFs of the velocity and its derivatives obey a power law, as opposed to an exponential one exhibited by Gaussian PDFs, with power law indices that sometimes, for viscoelastic flows, are low enough to imply unbounded fourth- (kurtosis), or even third-(skewness) moments of the distribution, what we can call "strong fat tails" behavior. We use Hill's estimator to evaluate the power law index of the tails, as well as statistical inference methods to perform hypothesis testing for the appropriateness of the power law fit. We have found that fat tails corresponding to power law tail distribution behavior are observed in the PDFs for both Newtonian and viscoelastic cases. However, viscoelasticity leads to PDFs that exhibit consistently fatter tails than the Newtonian ones and it is only in the presence of viscoelasticity that turbulence leads to "strong fat tails" as defined above. We infer that drag-reducing viscoelastic turbulence involves more infrequent and more correlated and more extreme events which makes DNS of viscoelastic turbulent flows much more computationally demanding than Newtonian DNS, requiring finer spatial resolutions, longer integration times, and larger computational domain sizes.