The good news is that you have a good 4-6 years of time to learn how to process that sort of material, and you aren't expected to be able to do it immediately. A professor once told me (about physics papers, but it translates into mathematical and CS papers fairly well) that eventually you start to read the math-heavy parts a bit like music -- you see familiar patterns, and you get the general idea without having to dig deep into the details.
Additionally, you'll find that the more classes you take, and the more reading you do really does prepare you for that next paper and that next step. You'll find that as you start specializing on a particular topic, most of the papers in your topic will become easier to read, simply because you have the experience and have gained the knowledge about the particulars over time. Furthermore, you'll start coming up with your own ideas in the subject, and this just happens to be the goal of graduate school!
There are lots of things (like bloom filters, k-means algorithms, and a lot lot much more terminologies) which we, normally, don't encounter...but are really crucial to understand papers.
The beauty is that you will start encountering them more, and you'll start understanding them more and more as you continue your education.
To answer your particular question,
Are there people like me who have done/are doing a Ph.D and had the same problem?
I still have difficulty getting through math-heavy papers (in CS), but I either re-read sections closely until I figure it out, or I ask someone to help, or I simply move on and hope that the rest of the paper fills in the details. I don't expect to understand everything technical that I read, but it becomes easier over time to get what you need out of a particular paper even if you don't get each and every detail.