Recently conducted clinical studies prove the utility of Coronary Computed Tomography Angiography (CCTA) as a viable alternative to invasive angiography for the detection of Coronary Artery Disease (CAD). This has lead to the development of several algorithms for automatic detection and grading of coronary stenoses. However, most of these methods focus on detecting calcified plaques only. A few methods that can also detect and grade non-calcified plaques require substantial user involvement. In this paper, we propose a fast and fully automatic system that is capable of detecting, grading and classifying coronary stenoses in CCTA caused by all types of plaques. We propose a four-step approach including a learning-based centerline verification step and a lumen cross-section estimation step using random regression forests. We show state-of-the-art performance of our method in experiments conducted on a set of 229 CCTA volumes. With an average processing time of 1.8 seconds per case after centerline extraction, our method is significantly faster than competing approaches.