alt Hacker Newsyeah, i've studied a lot of math and a lot of cs, and stats is tough. part of the problem is the terminology, and just giving a ton of complex machinery without telling you what it's actually doing. i've never learned that way, and it is very easy to feel like you're doing some sort of dark magic.
also, probability theory vs statistics is an important distinction: prob theory is a nice clean mathematical subject, while statistics is almost the philosophy of applying probability theory to the world.
Statistical reasoning isn't really motivated when it's taught, at least in the US. My schooling (I did jump around a bunch) assumed the student to have picked it up through vague balls-and-bins style problems taught in various units in various grade levels.
By the time I took my statistics class in undergrad math, coming from a similar background to you, they just sort of assumed you had a head for combinatorics and used that to develop everything else. I was a really good student in undergrad and statistics was my hardest class, I spent like 2x time on that class than any other class.
In grad school I took a class on complex system failure analysis and was quite apprehensive. My hope was that I could team up with a classmate to help with the math while I could work on the systems levels analysis. Turns out that because I understood systems really well, system failure offered me the intuition I needed to really understand statistics. I aced the class, published a moderately popular paper in distributed systems using what I learned, then went and took our graduate level statistics class widely known to be very difficult and aced it.
I think tacking statistical thinking on as an afterthought in curriculum is a huge mistake in the school system, especially so in the age of machine learning. I think for the average student statistical thinking is even more important than a lot of trigonometry.